Can you guarantee that if you have a group of five numbers you can pick out three that will add up to a multiple of 3?

  Improve

Yes. Here's why...

What we need to do is find five numbers out of which a combination of three can not be picked whose sum is divisible by three.

The easiest way to see whether or not that's possible is to look at all possible numbers as sets, grouped by their offsets from multiples of three. That gives us three sets:

a(x) = 3x + 0 = {0, 3, 6, 9, 12, 15, 18, 21, 24 ... }
b(x) = 3x + 1 = {1, 4, 7, 10, 13, 16, 19, 22, 25, ... }
c(x) = 3x + 2 = {2, 5, 8, 11, 14, 17, 20, 23, 26, ...}

There are two important things to note here:

1) First, any three numbers selected from one of those sets will add up to a multiple of three. This can be demonstrated very easily. Let's take set C. We'll pick three random numbers out of the selection, calling them x, y, and z. Their sum then would be:

3x + 2 + 3y + 2 + 3z + 2
= 3x + 3y + 3z + 6
= 3(x + y + z + 2)
which means that all possible selections will be a multiple of three. Now let's try that with set B:

3x + 1 + 3y + 1 + 3z + 1
= 3(x + y + z + 1)
again, all answers are multiples of three.

This is most obvious with set A, where the results would be expressed simply as:
3x + 3y + 3z
= 3(x + y + z)

This means that in order for our set of five numbers to meet the conditions we want, no more than two can be picked out of any of those three sets.

2) The second important note to look at is that if we pick a random number out of each of those sets, and add them together, they too will add up to a multiple of three. Here's the proof, again with our three random selections of (x, y, z):

a(x) + b(y) + c(z)
= 3x + 0 + 3y + 1 + 3z + 2
= 3x + 3y + 3z + 3
= 3(x + y + z + 1)

This means that we can't pick a number out of all three sets. Otherwise, a sum that's divisible by three can be found.


Now consider these facts together:

1. we have three sets that include every possible number that we can select
2. we can pick at most two numbers out of each of those sets
3. we can pick numbers out of at most two of those sets

These conditions can not be met if we want to pick five numbers. We can find four that meet this condition (a pair out of any two of the sets), but if we want to pick a fifth one, it must either come from the third set, breaking our limit of two sets, or from one of the ones we've already picked from, breaking our limit of two per set.

First answer by Its Me Ue. Last edit by Jacob ewing. Contributor trust: 49 [recommend contributorrecommended]. Question popularity: 1 [recommend question].