Pigeonhole Principle – Prove That for Any Set of 5 Integers, There is a Subset of 3 Integers Whose Sum is Divisible by 3

Question

How can I show that for any set of 5 integers, there is at least one subset of 3 integers whose sum is divisible by 3?

I tried to think about it using the pigeonhole principle but I don't quite get it.

Answer 1

One way to approach this is as follows: Let $q \in \Bbb N$ be given. Note that for every $q$, there exists some $x \in \Bbb N$ and some $v \in \{0,1,2\}$ such that $q = 3x + v$.

Now let $x_i \in \Bbb N, v_i \in \{0,1,2\}$ be given such that $q_i = 3x_i + v_i$ for all $(1 \leq i \leq 5)$ What we're trying to prove is that for every possible realization of this set of five variables we can find at least one combination of $v_a + v_b + v_c = v_6$ such that $a,b,c$ are all distinct and in $\{1,2,3,4,5\}$ and that $v_6$ is divisible by three.

Assume that there exist a combination of three $v_i (1 \leq i \leq 5)$ such that all three $v_i$ are equal. Without loss of generality we can assume these are $v_1,v_2,v_3$. Then we have that $q_1 + q_2 + q_3 = 3(x_1 + x_2 + x_3) + 3v_1 = 3(x_1+x_2+x_3 + v_1)$ Where me make use of the assumption that $v_1=v_2=v_3$. Clearly the sum $q_q + q_2 + q_3$ is devisible by three.

Now assume there exists no combination of three $v_i(1 \leq i \leq 5)$ such that all three are equal. It is trivial to show that now we have at least one $v_i$ for every possible realisation of $v_i$. Thus, without loss of generallity we can assume $v_1 =0, v_2=1, v_3=2$. We now obtain: $q_1 + q_2 + q_3 = 3(x_1 + x_2 + x_3) + v_1 + v_2 + v_3 = 3(x_1 + x_2 + x_3) + 3 = 3(x_1 + x_2 + x_3 + 1)$.

Which is clearly devisible by three. This completes the proof.

Note that this proof is only applicable for natural numbers. But the extention to integers shouldn't cause too much trouble.