1
$\begingroup$

How is it possible to prove with the use of the pigeonhole principle that in every set of 2012 different numbers that are bigger or equal to zero there is at least one subset that if you sum up its elements you get a number is a multiple of 2012.

thanks in advance

Ron .g.

$\endgroup$
4
$\begingroup$

Let $x_,x_2,...,x_{2012}$ be the 2012 integers. Consider the integers: $$x_1$$ $$x_1+x_2$$ $$x_1+x_2+x_3$$ $$.$$ $$.$$ $$.$$ $$x_1+x_2+...+x_{2012}$$ If one of these numbers is equivalent to $0$ mod 2012, then we re done. Otherwise , we find that two of these numbers must have the same remainder when divided by 2012.This is because these are 2012 numbers whose remainders when divided by 2012 form a subset of {1,2,...,2011} Let $x_1+...+x_i=x_1+x_2+...+x_j$ (mod 2012) (where $i<j$). Now we find that $\sum_{n=i+1}^{j} x_n=0$ (mod 2012), and this is the required subset.

$\endgroup$
  • $\begingroup$ @user51929: Note that this proves there is a contiguous subset that sums to a multiple of 2012, not just some subset. It also doesn't need that the numbers are different or positive, just that they are integers. It is a stronger result than requested. $\endgroup$ – Ross Millikan Dec 5 '12 at 22:15
0
$\begingroup$

MORE GENERAL. Prove in every set of $n$ different numbers that are bigger or equal to zero there is at least one subset that if you sum up its elements you get a number is a multiple of $n$.

Proof. Let $a_1,a_2, \cdots, a_n$ be the $n$ integers. Consider $n$ sums: $$S_1=a_1, S_2=a_1+a_2, S_3=a_1+a_2+a_3, \cdots, S_n=a_1+a_2+ \cdots a_n$$ Case 1. If in this $n$ sums, there is at least one sums is divisible by $n$. Q.E.D.

Case 2. If in this $n$ sums, there is no sums which is divisible by $n$. Hence, by Pigeonhole principle, there is exist $2$ sums $S_i,S_j \; (1 \le i<j \le n)$ such that $n|S_j-S_i$ or $n|a_{i+1}+a_{i+2}+ \cdots+ a_j$. We have Q.E.D.

$\endgroup$

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.