Additive number theory clarification

Question

For the question "Let $n$ be a positive power of $2$. Prove that from any set of $2n - 1$ positive integers, one can choose a subset of $n$ integers such that their sum is divisible by $n$."

The proof given is as follows from page 43 from the link https://cms.math.ca/crux/backfile/Crux_v12n03_Mar.pdf

Letting $n = 2^m$ , our proof is by induction on $m$. Clearly the result is valid for $m = 1$. Assume the result is valid for $n = 2^m$ Consider the case $n = 2^{m+1}$ . Since $2^{m+2} - 1 = 2^m + 2^m +(2^{m+1} - 1)$, by the inductive hypothesis we can always select three
disjoint subsets, each of $2^m$ numbers, from $2^{m+2} - 1$ numbers such that the sum of each subset is divisible by $2^m$ . Letting the three sums be $a\cdot (2^m) , b\cdot (2^m) , c\cdot(2^m)$ , at least two of the numbers $a,b,c$ have the same parity. By selecting the two sets corresponding to these numbers, we obtain $2^{m+1}$ numbers whose sum is divisible by $2^{m+1}$. Consequently, the result is valid for all positive integers $m$ by induction.

However, I can't understand the second half beginning with the parity part. Could someone please elaborate in depth?

Answer 1

Okay we want to prove that if we have a set of $2*2^m -1$ elements we can select $2^m$ elements so that their sum is $2^m$ (the $n$ just confuses everything.)

Okay, the proof goes as follows:

Letting $n = 2^m$ , our proof is by induction on $m$. Clearly the result is valid for $m = 1$. Assume the result is valid for $n = 2^m$ Consider the case $n = 2^{m+1}$ . Since $2^{m+2} - 1 = 2^m + 2^m +(2^{m+1} - 1)$, by the inductive hypothesis we can always select three
disjoint subsets, each of $2^m$ numbers, from $2^{m+2} - 1$ numbers such that the sum of each subset is divisible by $2^m$ . Letting the three sums be $a\cdot (2^m) , b\cdot (2^m) , c\cdot(2^m)$ , at least two of the numbers $a,b,c$ have the same parity. By selecting the two sets corresponding to these numbers, we obtain $2^{m+1}$ numbers whose sum is divisible by $2^{m+1}$. Consequently, the result is valid for all positive integers $m$ by induction.

"Clearly the result is valid for $m = 1$"

So if you have $2^1 =2$ then for any set of $2*2^1-1 = 3$ elements we can select $2^1= 2$ of them so that their sum is divisible by $2$. Pf: It there are two odd elements we can pick them. Their sum will be even and therefore divisible by $2$. If there aren't two odd elements that means there is at most one odd element which means there are at least two even elements. If so we pick those. Their sum will be divisible by $2$.

.... Now assume the statement is true for some $m$. That is for any set with $2*2^m -1$ elements we can select $2^m$ elements whose sum add to a multiple of $2^m$. We need to prove the statement is true for $m+1$.

"Since $\color{blue}{2*2^{m+1} - 1=}2^{m+2} - 1 = 2^m + 2^m +(2^{m+1} - 1)$by the inductive hypothesis we can always select three disjoint subsets, each of $2^m$ numbers, from $2^{m+2} - 1$ numbers such that the sum of each subset is divisible by $2^m$ "

So we have a set of $2*2^{m+1} -1 > 2*2^m - 1$ elements. We can choose $2^m$ elements from those whose sums add to $a\cdot 2^m$. We'll call those $2^m$ elements set $A$.

We have have $2*2^{m+1} -1 - 2^m = 3*2^m - 1 > 2*2^m - 1$ elements. We can choose $2^m$ elements from those whose sums add to $b \cdot 2^m$. We'll call those $2^m$ elements set $B$.

This leaves us with $3*2^m - 1 - 2^m = 2*2^m - 1$. And we can choose $2^m$ elements from those so that their sum add to $c \cdot 2^m$. We'll call those $2^m$ elements set $C$.

If either $a,b,c $ are all even or $a,b,c$ are all odd, or two of them are even and one is odd, or two of them are odd and one of them are even.

In other words, at least two of $a,b,c$ are the same parity.

Without loss of generality, we will assume $a$ and $b$ have the same parity. So $a+b$ is even (odd + odd = even. even + even = even).

So ....

We have a set with $2*2^{m+1} - 1$ elements. Set $A$ and set $B$ are $2^m +2^m = 2^{m+1}$ elements. They add up to $a\cdot 2^m + b \cdot 2^m = (a + b)\cdot 2^m$. $2|a+b$ so $2^{m+1}|(a+b)2^m$.

So we can select $2^{m+1}$ elements whose sum is a multiple of $2^{m+1}$.

So statement is true for $m +1$.

So we have proven this by induction.

Answer 2

This is actually true for any positive number n (not only positive power of 2). Here is the proof.

First, it is true for n prime.

The concept is, with the first number chosen, in the following steps, we always have two numbers to choose from that will create at least one additional possibility to make more numbers. So we'll finally be able to make all n different remainders that must include 0.

From now on, we assume that all the computation is on mod n. So, all the $2n-1$ numbers are considered as in the integer range [0, n-1]. First we arrange the numbers incrementally. Then, move the numbers from the $(n+1)^{th}$ through the $(2n-1)^{th}$ to the second line starting from the position 2. We assume that the two numbers at the same column of the two lines are different; otherwise, the n numbers between these two numbers are all the same. Choosing these numbers will do. Let the set of the numbers be $\{a_i\}_{i\in[1, 2n-1]}$ (incrementally in this order). Now, the n numbers in the first line has a sum. If we switch the two numbers in the same column, the sum of the first line will change. So, by choose changing or not changing a column, we'll get different sums. Let $s_k$ be the size of the set of the sums we can make with the $2^{nd}$ through $k_{th}$ columns switched or not switched, and $S_k=\{t_{ki}\}_{i\in[1, s_k]}$ be the set of sums. When k=1, $s_1=1$ (the original sum in $S_1$). We claim that with every additional column's switch, we'll be able to make at least one more sum. Since the two numbers of the same column are different, let $d_k=a_{k+1+n-1}-a_{k+1}=a_{k+n}-a_{k+1}\ne 0$. Now, $S_{k+1}=S_k \cup (S_k+d)$, where $S_k+d=\{t_{ki}+d\}_{i\in[1, s_k]}$. Obviously, $S_k\subset S_{k+1}$. We claim that $s_{k+1}>s_k$ if $s_k<n$. Actually, $\sum (S_k+d)-\sum S_k=s_k\cdot d$. If $S_{k+1}=S_k$, $s_k\cdot d | n$. However, since we assume n is prime, this is impossible when $0<s_k<n,\ 0<d<n$. So, the claim is proved.

For n non-prime, a similar procedure in the prior answers will prove that if the statement is true for n and m, then it is true for nm. This step is omitted.