|
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. |
||||
|
|
|
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. |
||||
|
