Show that from any five integers, one can always choose three of these integers such that their sum is divisible by 3.
+247 Let x be a multiple of 3.
There are 3 possible remainders for a number divided by 3: 0, 1 and 2. Since x is a multiple of 3 the numbers x+0, x+1, and x+2 will leave a remainder of 0, 1 and 2, respectivly, when divided by 3.
Lets look at the sets of numbers that will sum to a multiple of 3:
x, x, x
The sum is 3x which will always be a multiple of 3 because you are multiplyng by 3 and x is a multiple of 3.
x, x+1, x+2
Adding these numbers gets 3x+3, which will always be a multiple of 3.
x+2, x+2, x+2
The sum is 3x+6 which will be a multiple of 3 because both parts of the number are divisible by 3.
x+1, x+1, x+1
Sums to 3x+3, always a muliple of 3 for the above reasons.
It is impossible to have a set of numbers that does not have one of these cases in it.
If the set has one of each remainder, you can sum them to be a multiple of 3.
Lets try to make a set of numbers where none sum to a multiple of 3:
x, x, x+2, x+2
If you have two of 2 different remainders, if you add the third remainder you will have one of each and a multiple of 3. If you add one of the remainders you already have, you will have 3 times that remainder which will always be a multiple of 3.
