Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
@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. –  Ross Millikan Dec 5 '12 at 22:15

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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