Weirdly: adv. In a strikingly odd or unusual manner
< Older Blog - The Latest - Pick One - Show All - Newer Blog >

11-07-2010 Another good math puzzle

I saw another good little math puzzle today, and enjoyed it so much I thought I'd share it.

This came from a question on Wiki Answers, which I was glad to be able to answer. The question is:

Can you guarantee that in any set of five numbers, you can always find a set of three whose sum is divisible by three?
The answer to which is yes, and we can demonstrate that by disproving the opposite. In other words, we can show that it's impossible to create a set of five numbers in which there is no combination of three whose sum is divisible by three.

The first thing we need to do is think of our possible numbers as members of different sets. These sets will be whole numbers that are three apart from each other. There are exactly three such sets, and they are:

  1. a(x) = 3x + 0 = {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...}
  2. b(x) = 3x + 1 = {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, ...}
  3. c(x) = 3x + 2 = {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, ...}
You will see that these sets cover all of our whole numbers, and therefore the entire range of numbers that we can pick from for this problem

There are two important behaviors to note about these sets:

  1. If you take any three numbers out of any one of those sets, they will always add up to make a multiple of three. We can show this pretty easily. Let's start with our first set, a(). Because all members in that set are multiples of three, we know that all possible sums of that set will always be a multiple of three as well. In other words, 3x + 3y + 3z + ... will always be equal to 3(x + y + z + ...), and therefore, always divisible by three.

    The second set, b(), is not quite as obvious, but also pretty simple. Let's make an equation for the sum of any three numbers of that set. We'll call their indicies x, y, and z. Their sum then can be expressed as:

    • b(x) + b(y) + b(z)
    • = (3x + 1) + (3y + 1) + (3z + 1)
    • = 3x + 3y + 3z + 3
    • = 3(x + y + z + 1)
    Because the result is divisible by three - regardless of what x, y and z are, we know that this will be true for the sum of any three numbers in that set.

    This is also true for the third set, c():

    • c(x) + c(y) + c(z)
    • = (3x + 2) + (3y + 2) + (3z + 2)
    • = 3x + 3y + 3z + 6
    • = 3(x + y + z + 2)
    Again giving us that factor of three. This means that for our original conditions to be met, we can't have more than two numbers out of any one of those sets.

  2. If you take one number out of each of the three sets, and add them together, those too will also add up to a multiple of three. This can again be proven using the same method:

    • a(x) + b(y) + c(z)
    • = (3x + 0) + (3y + 1) + (3z + 2)
    • = 3x + 3y + 3z + 3
    • = 3(x + y + z + 1)
    This tells us that in order for our conditions to be met, we can't have a number from each of those three sets. In other words, We can only have numbers from two of our three sets.

Since we can only pick from two of the three sets, and can only pick two from each set, this means that the most numbers we can before meeting this condition is four. Which means the answer to our original question is yes.

< Older Blog - The Latest - Pick One - Show All - Newer Blog >