1
$\begingroup$

I came across a question in the pigeonhole principle that - Let S be a set of n integers. Show that there is a subset of S, the sum of whose elements is a multiple of n by pigeonhole.

How do I solve this question??

$\endgroup$
2
$\begingroup$

Consider the set $$\{ a_1, a_1+a_2, a_1 +a_2 +a_3,...,a_1+a_2+...+a_n\}$$

You have a set of $n$ elements.

If all remainders in dividing by $n$, are different, one of the remainders is $0$ and we are done.

Otherwise two remainders are the same. In this case the difference is a multiple of $n$ and as you see the difference is still a sum of some integers from $1$ to $n$

$\endgroup$
  • $\begingroup$ +1 However I think it would be natural to consider the set $$\{0,a_1,a_1+a_2,a_1+a_2+a_3,\dots,a_1+a_2+\cdots+a_n\}$$ of $n+1$ elements, so that there is only one case instead of two. $\endgroup$ – bof Apr 22 '18 at 19:01
  • $\begingroup$ good point if you consider the empty case as a valid solution. $\endgroup$ – Mohammad Riazi-Kermani Apr 22 '18 at 20:51
  • $\begingroup$ Of course the empty set is not a valid solution. The point is that, if we define $s_k=a_1+a_2+\cdots+a_k$ for $k=0,1,2,\dots,n$ (so that $s_0=0$) then we must have $s_i\equiv sj\pmod n$ for some $0\le i\lt j\le n$ and then we get a (nonempty) solution $a_{i+1}+\cdots+a_j\equiv0\pmod n.$ This is exactly your argument, it is just a neater presentation; the point is that the case $i=0$ does not have to be considered separately, it is just like all the other cases. $\endgroup$ – bof Apr 23 '18 at 0:30
  • $\begingroup$ OK, I got it now! Thanks. $\endgroup$ – Mohammad Riazi-Kermani Apr 23 '18 at 1:09

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.