A pigeonhole problem - find 2 equal sums out of 8 numbers 10 <= n <= 36

Question

i have to prove the following:

pick any 8 numbers within $10 \leq n \leq 36$

prove that you can find 2 equal sums using some or all of the 8 numbers you picked.

you cannot use any of the number twice.

for the numbers ${13, 18, 20, 21, 28, 29, 31, 35}$

i can write :

$13 + 18 = 31$

or

$29 + 20 = 21 + 28$

the only thing i managed to figure out is that it has something to do with

modulo, probably 7 but that's as far as i could stretch my aching mind.

thanks for your help

Oren

Answer 1

Firstly let $N = \{n\in\mathbb{N}: 10\leq n \leq36\}$.

Let your choice of 8 numbers be encoded in an indexing set $(i_n: n\in\mathbb{N})$, then the possible sums are bounded as shown below:

$$ 10+11 = 21\leq\sum_{n=1}^{2}N_{i_n}\leq\sum_{n=1}^{8}N_{i_n}\leq 260=\sum_{k=29}^{36}k$$

Or in other words, there are $260-21+1=240$ different sums (it's probably less than this but it doesn't matter).

Trivially since there is $(36-10+1)\cdot(36-10+1-1) = 27\cdot26 = 702$ ways I can pick any two distinct numbers from $N$, you are guaranteed to get at least $2$ pairs of numbers summing to the same sum since $\frac{702}{240}=2.925$.

Edit: I guess to fit your question, since there are 702 "pigeons" and 240 "holes", at least 2 "pigeons" must be in the same "hole".