Let there be $2n+1$ integers such that when one of them is removed, the sum can be divided into $2$ groups each with $n$ integers.

Question

Let $a_1,a_2,\cdots,a_{2n+1}$ be integers such that, if any one of them is removed, the remaining ones can be divided into two sets of $n$ integers with equal sum. Prove $a_1 = a_2 = \cdots = a_{2n+1}$

$Note:-$ The solution is mentioned in this website - https://www.fmf.uni-lj.si/~lavric/Santos%20-%20Number%20Theory%20for%20Mathematical%20Contests.pdf.

I understood the first three lines of the solution but however from the fourth line, I couldn't understand, why are all $a_k$ congruent mod $4$ ?

THE PROOF FROM THE WEBSITE - "As the sum of the $2n$ integers remaining is always even, no matter which of the $a_k$ be taken, all the $a_k$ must have the same parity. The property stated in the problem is now shared by $a_k/2$ or ($a_k −1$)/$2$, depending on whether they are all even, or all odd. Thus they are all congruent mod $4$. Continuing in this manner we arrive at the conclusion that the $a_k$ are all congruent mod $2^k$ for every $k$, and this may only happen if they are all equal."

https://math.stackexchange.com/questions/2920667/remove-any-number-and-the-remaining-numbers-can-be-partitioned-into-two-subsets — bof, Dec 26 '20 at 07:09
https://math.stackexchange.com/questions/1002267/after-removing-any-part-the-rest-can-be-split-evenly-consequences — bof, Dec 26 '20 at 07:11
well @bof i want the justification of the third line in the proof. — arnav_de, Dec 26 '20 at 09:04
If $a_k/2=2b_k$ are all even, then $a_k=4b_k=0\pmod{4}$; if they are all odd, $a_k-1=4b_k$ so $a_k=1\pmod{4}$, for all $k$. — Chrystomath, Dec 26 '20 at 09:49

score 1 · Accepted Answer · answered Dec 26 '20 at 09:59

Let, for each $i$, $S_i$ be the sum of the $a_j$ over the $1\leq j \leq 2n+1$ with $j \neq i$.

Clearly, if $1 \leq i,j \leq 2n+1$, $S_i+a_i=S_j+a_j$, ie $a_j-a_i=S_i-S_j$.

Now, for each $1 \leq i \leq 2n+1$, the $a_j$, $1 \leq j \leq 2n+1$ and $j \neq i$, can be split in two subsets of same sum, so $S_i$ is even. It follows that for each $1\leq i,j \leq 2n+1$, $a_i-a_j$ is even. Thus all the $a_i$ have the same parity.

Let there be $2n+1$ integers such that when one of them is removed, the sum can be divided into $2$ groups each with $n$ integers.

1 Answers1