A pigeonhole riddle

Question

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!

Answer 1

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.

Answer 2

It is being asked if John can always find from any $8$-set, two non-empty, proper, disjoint subsets having same sum.

There are $2^8-2=254$ non-empty, proper subsets. Hence $254$ possible sums for any $8$-selection.

The minimum and maximum sum for any non-empty, proper subset is $10$ and $30+31+\ldots+36=231$ respectively.

Hence due to Pigeonhole principle, John always wins.

Note that either John obtains two disjoints subsets right away or two non-disjoint subsets. In the latter case, he removes the common terms to obtain disjoint ones.