Show that from any five integers, one can always choose three of these integers such that their sum is divisible by 3.

Guest Jun 16, 2019

#1**+1 **

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.

power27 Jun 16, 2019