Let $n > 1$ be a positive integer and $a_1, a_2, \dots, a_{2n} \in \{ -n, -n + 1, \dots, n - 1, n \}$. Suppose \[ a_1 + a_2 + a_3 + \dots + a_{2n} = n + 1 \]Prove that some of $a_1, a_2, \dots, a_{2n}$ have sum 0.
Problem
Source: INAMO 2019 P8
Tags: combinatorics
03.07.2019 15:33
We will construct a permutation of $\{ a_1, a_2, \dots, a_{2n} \}$, that is $\{ b_1, b_2, \dots, b_{2n} \}$, satisfying \[ -n+2 \le \sum_{i=1}^k b_i \le n+1 \]for every $i \in \{ 1,2,\dots, 2n\}$. We construct it by picking one by one. For the base case $t=1$, just take $b_1$ as any positive term in $a_i$'s. Assume the property holds for $t=k$. We will find $b_{k+1}$ so the property also holds for $t=k+1$. Divide into cases: $\sum_{i=1}^k b_i \le 1$: Clearly, there is an unpicked positive number (Because their total sum is $n+1$, bigger than $1$). Take that number as $b_{k+1}$. $\sum_{i=1}^k b_i \ge 2$: If there is an unpicked term of $a_i$'s which is non positive, pick that as $b_{k+1}$. Else, every other unpicked term is positive, then we could simply take any of those terms as $b_{k+1}$, because if $\sum_{i=1}^{k+1} b_i > n+1$, then there exists an unpicked term which is negative (because $a_i$'s total sum is only $n+1$). Now consider $0, b_1, b_1 + b_2, \dots, b_1+b_2+\dots + b_{2n}$. There are $2n+1$ values, but they are bounded by $-n+2$ and $n+1$. Since there are only $2n$ integers in $[-n+2, n+1]$, so by PHP there are two terms which are equal. Easy to see this implies there exists some of $a_1, a_2, \dots, a_{2n}$ have sum $0$.
03.07.2019 15:40
Annoying and intetesting
03.07.2019 15:52
This problem is similar to day 1's problem 2...
05.01.2020 16:50
wrong solution.
24.06.2020 10:33
Is there any other way to do this