Pigeonhole Principle Application?

Question

OK, I just screwed this up on my discrete math final.

Make me feel dumb.

"If you choose any 5 numbers, there must be a way to sum the squares of 3 such that the result is evenly divisible by 3."

I get that if you choose any 5 numbers, either at least 3 of them are odd or 3 of them are even.

What I couldn't seem to figure out is how to show that the sum of the squares of 3 even or 3 odd numbers numbers is always divisible by 3....?

*sigh*

Yes, I know what mod is.

I definitely need sleep. :(

Answer 1

You were close. Instead of looking at the remainders after division by 2 (1 if odd, 0 if even), you should have considered division by 3.

All integers can be written as 3k, 3k + 1 or 3k + 2. (If you're wondering, "Why not 3k - 1 or 3k + 5?", the answer is that they are equivalent to 3k + 2, just for a different k.) Their squares are 9k^2, 9k^2 + 6k + 1, and 9k^2 + 12k + 4. These then can be reduced to 3k, 3k + 1, and 3k + 1, for different k's. Thus, squares are always evenly divisible by 3 or exactly one more than a multiple of 3.

So by the Pigeonhole Principle, there are 3 numbers that give 3k or 3 numbers that give 3k + 1. In the first case, choose those 3. In the second case choose those 3.

Your questions are so much more fun than those "Be my calculator" ones.

Answer 2

Okay, I don't think that the odd/even strategy is going to help.

You are starting with 5 numbers. Each number mod 3 is either 0, 1, or 2. If you square those, you get

(0 mod 3)^2 = 0 mod 3
(1 mod 3)^2 = 1 mod 3
(2 mod 3)^2 = 1 mod 3

So of the 5 numbers, each one is either 0 mod 3 or 1 mod 3 when squared. Because there are 5 numbers, then there must be at least 3 of one or the other (there's the pigeonhole principle). If you sum 3 numbers that are 0 mod 3, you get a number 0 mod 3. Likewise, if you sum 3 numbers that are 1 mod 3, you get a number 0 mod 3.

(Do you know what "mod" is? It just means that, for example, if you divide a number by 3 and get a remainder of 1, that original number is 1 mod 3. A number that is evenly divisible by 3 is congruent to 0 mod 3.)

Answer 3

An easy example of the pigeonhole principle involves the situation when there are five people who want to play softball, but only four teams. This would not be a problem except that each of the five refuses to play on a team with any of the other 4. To prove that there is no way for all five people to play softball, the pigeonhole principle says that it is impossible to divide five people among four teams without putting two of the people on the same team. Since they refuse to play on the same team, at most four of the people will be able to play.

Although the pigeonhole principle may seem to be a trivial observation, it can be used to demonstrate possibly unexpected results. For example, there must be at least two people in London with the same number of hairs on their heads. Demonstration: a typical head of hair has around 150,000 hairs. It is reasonable to assume that no one has more than 1,000,000 hairs on their head. There are more than 1,000,000 people in London. If we assign a pigeonhole for each number of hairs on a head, and assign people to the pigeonhole with their number of hairs on it, there must be at least two people with the same number of hairs on their heads.


The pigeonhole principle often arises in computer science. For example, collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. No hashing algorithm, no matter how clever, can avoid these collisions. This principle also proves that there cannot be a lossless compression algorithm that will compress any file by a certain amount. If it could then two files would be compressed to the same smaller file and restoring them would be ambiguous.

Several additional examples are given by Grimaldi