# How to recognize a pigeonhole problem?

I'm going to split this into 2 questions, the first I think might have an answer, the second may not.

First, is there a general way to recognize a pigeonhole problem as such? I mean are there some general traits which characterize a pigeonhole problem?

Second, once you've recognized the type of problem, is there a systematic way of figuring out what the holes and pigeons are, or is it just a eureka kind of thing?

-

I think what OP meant as a question is more elementary, i.e. in a course context.

In general, the reason why we think of a pigeonhole argument is because we think there is enough elements we need to choose from some lot for these elements to get something out of this lot. Let's just take an example.

Suppose you choose randomly points in an equilateral triangle with sides length $2$. Prove that wherever we take $5$ points inside this triangle, there exists at least a pair of points with distance between them less than $1$.

The key here is to see why does $5$ points is enough to know that two points will be close enough.

Suppose we took $3$ points first. To make sure they're as far as possible, let's put them at the vertices of the triangle. Now we want to add a fourth point. Well, if it's as far as possible from the four others, then it has to be in the middle. But now where do I put the fifth point?

Solution : If you divide the triangle of length $2$ into four triangles by tracing lines between the midpoints of the sides of the original triangle (i.e. by dividing it into four triangles of side length $1$), you realize that wherever I put the $5^{\text{th}}$ point, it has to lie in one of those triangles, and two points inside such a triangle have distance less than $1$. Here! We've found pigeonholes : the triangles of length $1$. If these are the pigeonholes, then we're trying to put $5$ points in $4$ pigeonholes, hence at least $2$ points are in the same triangle, so they have a distance less than $1$.

The idea behind my research of the solution was that I was trying to "find some optimal position" for the points, and then realized "there's not enough space for them". The part where you notice there's not enough room for all your things is where the pigeonhole principle usually does the trick.

To answer your second question, to choose the pigeonholes, you need to make them work for what you're looking for. For instance, here I wanted pigeonholes which ensured me that two points inside those regions gave me my result. Triangles did the trick so I just guessed them from looking at the problem long enough.

For another example, if you're looking at, say, trying to say that some set of numbers must contain a pair whose difference must be $n$, then it might be a good idea to pair up $k$ and $k+n$ together, since their difference is $n$. The idea here is simply to construct pigeonholes in such a way that when you have two things in your pigeonhole, you're able to solve your problem. Sometimes adding pigeonholes with less than two things in it might be pertinent though (to eliminate trivial cases), and in this case we know that two things cannot have been taken in this pigeonhole since it has only one thing in it.

Hope that helps,

-

Well, let me keep away from formal terminology and formulas. In essence, the pigeonhole principle says the following. If you are trying to sort $n$ objects into $m$ boxes, and if $n$ is bigger than $m$, then you'll end up putting at least two objects in some one of the $m$ boxes. This should answer your second question as well.

The Wikipedia gives a few cute examples here: http://en.wikipedia.org/wiki/Pigeonhole_principle

So, if you you're investigating some sort of association between two collections of objects, then if one collection is larger than the other, then your association must associate at least two objects in one collection to the same object in the other.

This, however, illustrates the bare bones pigeonhole principle. Now, suppose you're working on a complicated problem, and after many days of mental agony and two stacks of scratch paper, you reduce the problem to the pigeonhole principle. Does this figure into your question? Does this beg the question "how should I have recognized in the very beginning that there is pigeonhole principle involved?" Well, the answer is: mental agony and two stacks of scratch paper (and most likely an ingenious trick somewhere along the way).

Maybe I can draw a parallel with software design here (since you seem to be more of a programmer). Suppose you're trying to design an algorithm, and after many days of thinking, you realize that there is a clever way to use a well known design pattern. Is there an algorithm for recognizing something like this? In simple cases, yes. But most of the time - no.

Mathematics, for the most part, is not "algorithmic" in the sense of your question. Hope this answer helps.

-