11072010 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:
 a(x) = 3x + 0 = {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...}
 b(x) = 3x + 1 = {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, ...}
 c(x) = 3x + 2 = {2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, ...}
There are two important behaviors to note about these sets:

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)
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)

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)
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.