Prove that for any set of 5 integers, there is at least one subset of 3 integers whose sum is divisible by 3 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.
 A: 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.
A: Suppose the numbers are $x_1, x_2, x_3, x_4$, and $x_5$. For each $i$, let $r_i$ be the unique number $r_i \in \{0,1,2\}$ such that $r_i \equiv x_i \pmod 3$. Then we need to show that every possible instance of the list $r_1, r_2, r_3, r_4,r_5$ contains three numbers whose sum is congruent to $0$ modulo $3$.
The first thing to notice is that all three numbers $0,1$, and $2$ cannot occur in the list at the same time, since $0+1+2 \equiv 0 \pmod 3$
So you must have a list of 5 numbers chosen from one of the sets $\{0,1\}, \{0,2\}$, or $\{1,2\}$. By the pigeon-hole principle one of those numbers must occur at least three times. Since $0+0+0 \equiv 1+1+1 \equiv 2+2+2 \equiv 0 \pmod 3$, then there will always exist a subset of three numbers whose sum is a multiple of three.
A: Working from the comments, we're trying to fit $5$ integers into $3$ different remainder classes. So think of the integers as elements and each possible remainder as a box. Now the pigeonhole principle gives that either there will be $3$ or more integers in one remainder class, or that there is at least one integer in all of the classes.
If it's the first possibility then just picking the set of $3$ integers in the one remainder class will give a sum divisible by $3$. If it's the second possibility then we choose for our set one element from each remainder class, and the sum will once again give us 3.
To see this remember that for any $z\in \mathbb{Z}$ we have that $$z=3q+x$$
where $q$ is an integer and $x\in \{0,1,2\}$.
A: The set of three numbers to give non multiple of $3$ sum can have $6$  possibilities. $(0,0,1),(0,0,2),(0,1,1),(0,2,2),(2,1,1),(2,2,1), $ Where the elements of set represent modulo $3 $ of actual numbers. For any possibility, a set of $3 $ numbers can be made to get sum multiple of $3$. For example $ (0,1,1)$ if two others numbers have $1$ or $2$,change the set accordingly as $ (1,1,1) $ or $(0,1,2) $ respectively. Or if both numbers are $ (0,0 )$ then the set of $3$ zeros. Same logic can be applied for other possibilities.
