### pigeonhole principle

09Feb10

OK, so as many know, the common pattern for the three problems from the last post is called the “Pigeonhole principle”, and it’s deceptively simple: it says that if you have $n+1$ pigeons and you are trying to fit them into $n$ pigeonholes, then there exists at least one pigeonhole with 2 pigeons in it. Sounds simple enough, but then how do you apply this? The trick is to identify and properly define the pigeons, and also define the pigeonholes. In this case, the buckets are the different possible remainder values modulo 11: there are of course 11 pigeonholes.
The 12 distinct integers are the pigeons. And so there exists a pigeonhole with two pigeons in it: since they are distinct integers, their difference is a multiple of 11 (of course, had they been the same number, that would also be true, since 0 is divisible by 11).

What about the problem with the trees? You could have 600,000 pigeonholes, one pigeonhole for each possible value of (number of pine cones in a tree); there are only 600K, because 600K is the max value for the number of pine cones, according to the problem (as my friend Bernard pointed out, this is a wild over-estimate). The pigeons in this problem are the different trees: put a tree in the pigeonhole corresponding to how many pine cones it has. Since there are 1M trees, you have way more than 600K, and so you’ve got many pigeons crammed in the same holes (at least 400K repeats, as Susan’s daughter Evelyn pointed out – great job, Evelyn!).

What about the last problem? This is a slightly tricky one. For now, I’ll give a hint: Let Timer 1 be the timer that goes off every $x$ seconds, where $x$ is irrational. If I knew that there was an integers $k$ and $m > k$ so that the $k$-th and $m$-th firings of Timer 1 happened within $\mu$ seconds of each other, then this means that every $(m-k)$ firings are exactly $\mu$ seconds apart.

If we’re clever, we can get $\mu < \epsilon$, and so you could imagine traversing the face of a clock $\mu$ seconds at a time (basically ignoring all firings of Timer 1 except the ones that occur at $k$, $k+ (m-k)$, $k + 2(m-k)$, etc, seconds). How could this help us solve the problem?

Some things to focus on in your solution:

• what are the pigeonholes?
• what are the pigeons?
• why do we insist that $x$ is irrational?