+0  
 
0
276
4
avatar

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

 Jun 16, 2019
 #1
avatar+224 
+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.

 Jun 16, 2019
 #2
avatar
+1

Thanks so much!

Guest Jun 16, 2019
 #3
avatar
0

But wait, what about $3x+5?$

Guest Jun 16, 2019
 #4
avatar+224 
0

That wouldn't be divisible by 3, but there would always be another combination of 3 numbers in the set that would be divisible by 3.

power27  Jun 17, 2019

24 Online Users

avatar
avatar
avatar