Prove that for any set containing $2047$ positive integers, there exists $1024$ positive integers in the set such that the sum of these positive integers is divisible by $1024$.
Problem
Source: 2015 Taiwan TST Round 1 Quiz 2 Problem 1
Tags: Taiwan, combinatorics, Taiwan TST 2015
12.07.2015 14:59
This is Erdos-Ginzburg-Ziv Theorem with $n=1024$. Erdos-Ginzburg-Ziv Theorem: For any set of $2n-1$ positive integers, there exists $n$ positive integers in the set such that the sum of these positive integers is divisible by $n$ This theorem is trivial for $n=2$. Claim: If this theorem is true for $n=a$ and $n=b$, it is also true for $n=ab$. Proof. Take $a$ numbers from $2ab-1$ numbers $2b-1$ times so that each time, the sum of the $a$ numbers taken is a multiple of $a$. We can do this because this theorem is true for $n=a$. Since there are $2b-1$ numbers, we can choose $b$ of them so the sum of those $b$ numbers are a multiple of $b$. So in total, we chose $ab$ numbers so that the sum of those numbers is a multiple of $ab$. $\blacksquare$ Therefore, it holds for $n=1024$. $\blacksquare$
02.01.2016 17:53
if we replace 1024 into n , 2047 into 2n-1 is the problem still correct ??
02.01.2016 20:47
andywu wrote: if we replace 1024 into n , 2047 into 2n-1 is the problem still correct ?? Did you not read the above post...
08.01.2020 22:25
Alternative Proof: Claim: Let S be a set of integers such that $|S|=2^n - 1$, Then there is a subset T of S such that $|T|=2^{n-1}$ and $2^{n-1}$ divides the sum of the elements of T. Proof: We prove this by induction on n. Note that $n=2$ is trivial. Suppose it is true for $n=k$. So in Set S choose 2 disjoint sets of $2^{k}-1$ numbers. By induction Hypothesis there exists : $A=\{A_1,A_2,....,A_{2^{k-1}}\} ; B=\{B_1,B_2,....,B_{2^{k-1}}\}$ such that : $2^{k-1}\vert A_1+A_2+.... A_{2^{k-1}}$ and $2^{k-1} \vert B_1+B_2+ ...... B_{2^{k-1}}$ Let $A_1+A_2+.... A_{2^{k-1}}=A2^{k-1}$ and $B_1+B_2+ ...... B_{2^{k-1}}=B 2^{k-1}$ Now let $X=\{A_1,A_2,....,A_{2^{k-1}},B_1,B_2,....,B_{2^{k-1}}\}$. Note that $|S/X|=2^k$ . So again there exists a subset C of S disjoint with A and B such that : $C=\{C_1,C_2,....,C_{2^{k-1}}\}$ and $2^{k-1}\vert C_1+C_2+.... C_{2^{k-1}}$ Let $C_1+C_2+.... C_{2^{k-1}}=C 2^{k-1}$. Now by PHP some 2 of A,B,C have same parity. WLOG A and B have same parity. Then $2^k \vert A_1+A_2+.... A_{2^{k-1}}+B_1+B_2+ ...... B_{2^{k-1}}$. So X is the desired set. This completes our induction step. So the claim is proved. Now note that n=11 in the claim gives us the desired result.