Show that from any five integers, one can always choose three of these integers such that their sum is divisible by 3.
+26367 Show that from any five integers,
one can always choose three of these integers such that their sum is divisible by 3.
Five integers have a remainder of 0 or 1 or 2 if they become divisible by 3:
\(\begin{array}{|c|c|c|c|} \hline & & & \text{one choose three} \\ \text{remainder 0} & \text{remainder 1} & \text{remainder 2} & \text{of these is divisible by 3} \\ 0 \pmod{3} & 1 \pmod{3} & 2 \pmod{3} & \text{sum of the remainder} \\ \hline 0 & 0 & 5 & 2+2+2 \\ 0 & 5 & 0 & 1+1+1 \\ 0 & 4 & 1 & 1+1+1 \\ 0 & 3 & 2 & 1+1+1 \\ 0 & 2 & 3 & 2+2+2 \\ 0 & 1 & 4 & 2+2+2 \\ \hline 1 & 0 & 4 & 2+2+2 \\ 1 & 4 & 0 & 1+1+1 \\ 1 & 3 & 1 & 1+1+1 \\ 1 & 2 & 2 & 0+1+2 \\ 1 & 1 & 3 & 2+2+2 \\ \hline 2 & 0 & 3 & 2+2+2 \\ 2 & 3 & 0 & 1+1+1 \\ 2 & 2 & 1 & 0+1+2 \\ 2 & 1 & 2 & 0+1+2 \\ \hline 3 & 0 & 2 & 0+0+0 \\ 3 & 2 & 0 & 0+0+0 \\ 3 & 1 & 1 & 0+0+0 \\ \hline 4 & 0 & 1 & 0+0+0 \\ 4 & 1 & 0 & 0+0+0 \\ \hline 5 & 0 & 0 & 0+0+0 \\ \hline \end{array}\)
+128407 Here's my attempt....
We only need to worry about 3 cases.....for.....if 3 or more of the integers are multiples of 3, we can select any three of those to have a sum which is a multiple of 3.....
Case 1.....Two of the integers are multiples of three .....let R2 = (an integer with a remainder of 2 when divided by 3) and R1 = (an integer with a remainder of 1 when divided by 3 )
So we have the following possibilities for the other three integers
R2 R2 R2 just select these three......
R2 R2 R1 select one of the R2's, the R1 and one of the other integers that is a multiple of 3
R1 R1 R2 select the R2, one of the R1's and one of the other integers that is a muliple of 3
R1 R1 R1 select these
Case 2 ....Only one integer is a multiple of 3...so....we have these posiibilities for the other four
R2 R2 R2 R2 select any 3 of these 4
R1 R2 R2 R2 select the 3 R2's
R! R1 R2 R2 select one of the R1's, one of the R2's and the other multiple of 3
R1 R1 R1 R2 select all 3 R1's
R1 R1 R1 R1 select any 3 of these 4
Case 3....No integer is a multiple of 3.....we have
R2 R2 R2 R2 R2 select any 3 of these
R2 R2 R2 R2 R1 select any 3 of 4 R2's
R2 R2 R2 R1 R1 select all the R2's
All the remaining situations will have at least 3R1's....so.....we can guarantee a sum that is a multiple of 3 by selecting from them
