Using pigeon hole principle show that among any $11$ integers, sum of $6$ of them is divisible by $6$.

I thought we can be sure that we have $6$ odd or $6$ even numbers among $11$ integers.Suppose that we have $6$ odd integers. Obviously sum of these $6$ odd numbers is divisible by $2$, so it remains to show that this sum is divisible by $3$ as well. But how?

up vote 3 down vote accepted

We first show that among any 5 integers, sum of 3 of them is divisible by 3. The residue classes modulo 3 are $[0], [1], [2]$. By Pigeonhole principle, we have two cases:

  1. each of these residue classes must have atleast one of the five integers, or
  2. one residue class must have 3 of these 5 integers belonging to it.

In the former case, let $x_0 \equiv 0 \mod 3$, $x_1 \equiv 1 \mod 3$ and $x_2 \equiv 2 \mod3$. Then summing $x_1, x_2, x_3$, we get, $x_1 + x_2 + x_3 \equiv 0 \mod 3$.

In the latter case, we have 3 integers among the 5, say $x_1, x_2, x_3$ such that, $x_1 \equiv x_2 \equiv x_3 \equiv k \mod 3$, again summing these three we get $x_1 + x_2 + x_3 \equiv 3k \equiv 0 \mod 3$.

This proves that among any 5 integers, sum of some 3 of them is divisible by 3.

Now, we have 11 integers. By the previous result, we can choose 3 of them such that there sum is divisible by 3. Denote this sum by $s_1$. Now, we are left with 8 integers, again, choose 3 of them such that there sum is divisible by 3. Denote this by $s_2$. Now, we are left with 5 integers. Choose $s_3$ similarly.

Thus we have 3 sums: $s_1, s_2, s_3$ (each of which are sums of 3 integers). These sums are divisible by 3. So, each of these sums are congruent to either 0 or 3 modulo 6.

Now, since there are 3 sums, and two residue clases ($[0], [3]$), by Pigeonhole principle, one residue class must have two sums belonging to it. Let $s_i$ and $s_j$ be those sums. Either, $s_i \equiv s_j \equiv 0 \mod 6$ or $s_i \equiv s_j \equiv 3 \mod 6$. In both the cases, $s_i + s_j \equiv 0 \mod 6$.

Since, $s_i$ and $s_j$ are both sum of 3 integers, $s_i + s_j$ is a sum of 6 integers (which is divisible by 6). This completes the proof.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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