John offers Dean the following challenge:
Dean would choose 8 natural numbers so that $10\leq n \leq 36$.
If John manages to create two equal sums using only numbers that Dean chose, at most once each, he wins.Assuming John has adequate time to check all options, will he always win? and why?
My thoughts were counting the number of options that Dean has for choosing 8 numbers, which is $27 \choose 8$, and also counting the number of options John has of creating sums, which is $\binom{27}{8}\cdot\sum^8_{i=2} \binom{8}{i}$. But that doesn't bring me anywhere.
I feel like it's true that John would always win, and I know I need to use the pigeonhole principle somehow, which means showing that for sure there are more possible ways to arrange sums than the number of sums possible. So, there are at least two arrangements for the same sum. (By arrangement for the same sum I mean two different combinations of numbers that summed give the same answer).
But I'm kind of stuck there.
Would appreciate assistance!
Best Answer
You can compute the maximum sum $S_M=36+35+34+33+32+31+30+29=260$ and the minimum sum $S_m=10+11=21$ (assuming we always have to sum at least two numbers). This means that any solution of the sum $S$ of any combination of the eight numbers will be $S_m \leq S \leq S_M$. From $S_M-S_m=239$ we get the number of different sums we can obtain from the combination of those numbers.
On the other hand, there are $\sum^8_{i=2} \binom{8}{i}$ possible sums from the 8 numbers chosen. It is enough to show that $\sum^8_{i=2} \binom{8}{i}>239$ in order to prove, by the Pigeonhole Principle, that there will always be a sum $S$ which can be computed in at least two different ways using different combinations of those 8 numbers.