Prove: A 9 element subset of ${1,2,...,99}$ must have two distinct subsets with the same sum.

Question

APMO 2014 Problem 4:

Prove: A 9 element subset of ${1,2,...,99}$ must have two distinct subsets with the same sum.

---

I am having a lot of trouble with this problem. The official solution: https://cms.math.ca/Competitions/APMO/sol/apmo2014-sol.pdf, as usual, does not provide motivation, so I can't learn anything from it.

Here are some easy observations:

There are $511$ nonempty subsets of the 9 element set. The problem is solved by pigeonhole if we can show that such a set must generate less than $511$ distinct subset sums.

The weakest bound on the number of distinct subset sums is:

$(99+...+91)-(9+..+1)=810$

If you find a solution, please include the motivation.

Answer 1

NOTE: As mentioned in the comments, the problem I solve below may not be the one given in the exam.

This approach differs from that in the solution manual.

Let $a_i$ be the ordered elements of any 9-element subset.

If $a_1+a_2+\ldots+a_7 \leq 99$, you have at least 128 (= $2^7$) sums less than 99, so there must be a repeat by the piegonhole principle.

We now consider cases:

• If $a_1+\ldots+a_7 \geq 100$, but $a_1+\ldots+a_6 \leq 99$, then $a_7 \geq 18$

$a_1+\ldots+a_7 \geq 100$ and $a_8+a_9 \geq 19+20$, so total $\geq 139$

$a_1+\ldots+a_6 \leq 99$ and $a_7+\ldots+a_9 \leq 97+98+99$, so total $\leq 393$

255 possible sums, but 512 possible combinations, so pigeonhole.

• If $a_1+\ldots+a_6 \geq 100$, but $a_1+\ldots+a_5 \leq 99$, then $a_6 \geq 20$

$a_1+\ldots+a_6 \geq 100$ and $a_7+\ldots+a_9 \geq 21+22+23$, so total $\geq 166$

$a_1+\ldots+a_5 \leq 99$ and $a_6+\ldots+a_9 \leq 96+97+98+99$, so total $\leq 489$

324 possible sums, 512 possible combinations, pigeonhole.

• If $a_1+\ldots+a_5 \geq 100$, but $a_1+..+a_4 \leq 99$, then $a_5 \geq 22$

$a_1+\ldots+a_5 \geq 100$ and $a_6+\ldots+a_9 \geq 23+24+25+26$, so total $\geq 198$

$a_1+\ldots+a_4 \leq 99$ and $a_5+\ldots+a_9 \leq 95+96+97+98+99$, so total $\leq 584$

387 possible sums, 512 possible combinations, pigeonhole.

• If $a_1+\ldots+a_4 \geq 100$ but $a_1+..+a_3 \leq 99$, then $a_4 \geq 27$

$a_1+\ldots+a_4 \geq 100$ and $a_5+\ldots+a_9 \geq 28+29+30+31$, so total $\geq 218$

$a_1+\ldots+a_3 \leq 99$ and $a_4+\ldots+a_9 \leq 94+95+96+97+98+99$, so total $\leq 678$

461 possible sums, 512 possible combinations, pigeonhole.

• If $a_1+\ldots+a_3 \geq 100$ but $a_1+a_2 \leq 99$, then $a_3 \geq 35$

$a_1+\ldots+a_3 \geq 100$ and $a_4+\ldots+a_9 \geq 36+37+38+39+40$, so total $\geq 290$

$a_1+a_2 \leq 99$ and $a_3+\ldots+a_9 \leq 93+94+95+96+97+98+99$, so total $\leq 771$

482 possible sums, 512 possible combinations, pigeonhole.

• If $a_1+a_2 \geq 100$, $a_2 \geq 51$

$a_1+a_2 \geq 100$ and $a_3+\ldots+a_9 \geq 52+53+54+55+56+57+58$, so total $\geq 485$

$a_1+\ldots+a_9 \leq 91+92+93+94+95+96+97+98+99$, so total $\leq 855$

371 possible sums, 512 possible combinations, pigeonhole.