Suppose $X = \begin{Bmatrix} x_{1}, & x_{2}, & x_{3}, & x_{4}, & x_{5} \end{Bmatrix}$ is a set of 5 distinct non-negative integers, with a set-sum of $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 51$
Show for all solutions of X there is a at least one sub-set of size 4 that has a sum of at least 42.
Also, how many different solutions are there for X, where order doesn't matter. For example, {1, 2, 3, 4, 42} is not a different solution from {42, 1, 2, 3, 4}.
I'm just a bit stuck on some of these questions for university at the moment, we were given an example solution, to the main question, which is the sub-set one.
But I feel like it wasn't the best proof. Also I'm having a hard time figuring out how you would find out how many different solutions there are, if order doesn't matter. I was using "stars and bars" earlier to figure it out if order did matter.
For the subset problem, notice that we can find a subset of 4 with sum 42 if the smallest number is 9 or less (since then we take all the other numbers). Yet it's impossible for the smallest number to be 10 (or larger), since then the minimum sum is
$$10+11+12+13+14=60$$
Therefore, the smallest number is at most 9, and the result follows.
For the other problem, here's a hint that'll help if you can count the ordered solutions: since all the numbers in an ordered solution are distinct, there are exactly $5! = 120$ ordered solutions per unordered solution. Problem is, you can't use stars and bars directly, since stars and bars doesn't necessarily give you distinct nonnegative integers. You'll have to do some casework to get the answer.