2
$\begingroup$

Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$.

My approach: Let $a_1,a_2,\ldots,a_{2^{n+1}-1}$ positive integers numbers. Define, $s_j=a_1+a_2+a_3+\ldots+a_{2^{j+1}-1}$, $j\in\{1,\ldots,n\}$.

If any of the $2^{n+1}-1$, $s_j$, are divisible by $2^n$, we are done.

In case contrary, $s_j$ have a remainder $1,2,3,\ldots,2^{n}-1\mod(2^n)$. And, we know that $2^{n+1}-1>2^n-1$, so by Pigeonhole Principle, there exist a tleast two $s_j$ such that has a same remainder ($\mod(2^n)$), i.e., if $p<q$, then $$s_q-s_p=a_{2^{p+1}}+a_{2^{p+1}+1}+\ldots+a_{2^{q+1}-2}+a_{2^{q+1}-1}\equiv 0\mod(2^{n})$$

So, the set $\{a_{2^{p+1}},a_{2^{p+1}+1},\ldots,a_{2^{q+1}-2},a_{2^{q+1}-1}\}$ is the set we need. I know, this answer doesn't be right, but is the idea I have to occupy Pigeonhole.

EDIT: Both answers were very good, but, how I could occupy the pigeonhole principle in this problem?

$\endgroup$
  • $\begingroup$ Do they have to be distinct elements in the sum? $\endgroup$ – Andrew Whelan Jul 24 '16 at 1:33
  • $\begingroup$ @Andrew it'd be pretty easy if not. You could just pick the same element $2^n$ times. $\endgroup$ – Matt Samuel Jul 24 '16 at 1:39
  • $\begingroup$ I think he means if it is possible to repeat an element more than once. $\endgroup$ – Jorge Fernández Hidalgo Jul 24 '16 at 1:39
  • $\begingroup$ @AndrewWhelan In the problem doesn't says nothing about it. So, I suppose should to be distinct elements. $\endgroup$ – MathUser Jul 24 '16 at 1:40
  • 1
    $\begingroup$ I added an answer explaining the precise relation to EGZ. One can recycle the easier part of the EGZ proof to solve this. @user4759923 $\endgroup$ – zyx Jul 24 '16 at 2:36
5
$\begingroup$

We proceed via induction over $n$.

The base case is $n=1$ and it is trivial, we have $3$ numbers, so clearly we can pick two with the same parity.


Inductive step:

Split the $2^{n+1}-1$ elements into two groups of size $2^{n}-1$ and an extra element.

By the inductive hypothesis we can pick two groups of $2^{n-1}$ elements from each group, with sum divisible by $2^{n-1}$. If these sums are congruent $\bmod 2^{n}$ we are done (just take the union).

Otherwise notice we have $2^{n+1}-1-2^{n-1}-2^{n-1}=2^n-1$ elements that are in none of the two groups. So by the inductive hypothesis we can form a third group of $2^{n-1}$ elements with sum divisible by $2^{n-1}$. This sum must be congruent $\bmod 2^n$ to one of the other two groups.

$\endgroup$
  • 1
    $\begingroup$ It can be slightly reworded, if we have $2^n-1$ elements we can extract a subset of $2^{n-1}$ elements with sum divisible by $2^{n-1}$. We can use this to extract three disjoint subsets of size $2^{n-1}$ and sum which is either $0$ or $2^{n-1}\bmod 2^n$. Take two which are congruent $\bmod 2^n$, their union does the trick. $\endgroup$ – Jorge Fernández Hidalgo Jul 24 '16 at 1:58
  • $\begingroup$ Very nice answer, but I have a confusion with your last phrase "This sum must be congruent $mod(2^{n})$ to one of the other two groups". Thanks again for your answer! $\endgroup$ – MathUser Jul 25 '16 at 3:17
  • $\begingroup$ Yeah, we have three groups. They are $A,B$ and $C$. Each of them has a sum that is either $0$ or $2^{n-1}\bmod 2^n$. So there are two groups that are congruent $\bmod 2^n$. Their union is the set we need. $\endgroup$ – Jorge Fernández Hidalgo Jul 25 '16 at 3:23
1
$\begingroup$

As suggested in the comments this is Erdos-Ginzburg-Ziv theorem for a power of $2$.

The proof of E-G-Z has an easy inductive part, that if the theorem is true for $p$ and $q$ it is true for $pq$, and a nontrivial base case of proving the theorem true for primes. Here the prime is $2$ so the base case is true by inspection. The proof of the multiplicative property is the same whether or not $p=q$ or if they are powers of $2$.

https://en.wikipedia.org/wiki/Zero-sum_problem

$\endgroup$
  • $\begingroup$ Thanks for your answer!, but exist other method for prove this?? I think the pigeonhole principle is enough. $\endgroup$ – MathUser Jul 26 '16 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.