Pigeonhole Principle — introduction — RMO and INMO

The following is a very brief introduction to the Pigeonhole Principle, which is simple, yet profound. It seems to be embedded in common sense, but does wonders when applied to several problems, pure and applied.

If the average weight of a students in a school classroom is 41 kg., then there is some student who weighs at least 41 kg. and some student who weighs at the most 41 kg. In fact, if there is one student with weight larger than 41 kg, then there must be some other student whose weight is less than 41 kg. There are four suits (spades, hearts, diamonds and clubs in the hierarchy) in a pack of 52 cards where every bridge player receives 13 cards in the hand. I was told of a story of a mathematician from a prestigious research institute who was taken out to play bridge by his bridge loving friend. No matter how the thirteen cards are dealt to you, said our friend to the mathematician, in some suit, you must receive at least 4 cards. The mathematician could not see this for some time and when he was convinced, he exclaimed, “Oh, that follows from the Pigeonhole Principle!” An average bridge player, who loves the game of bridge, is hardly aware that this fact is a consequence of the Pigeonhole Principle. In some cases, this principle is too obvious and too commonsense (perhaps, like the game of bridge) to be given the status of a principle. In its most general form, following are statements that go under the name “Pigeonhole Principle”:

(a) Simplest form: When n+1 pigeons are to be put in n boxes, there is at least one box that receives two or more pigeons.

(b) Slightly more profound: If we put kn+1 objects In n boxes, then some box must receive k+1 or more objects.

(c) Equivalently: If n non-negative integer quantities have an average strictly greater than \alpha, then there must be at least one quantity whose value is at least [\alpha ], where [x] denotes the smallest integer greater than or equal to x.

All those statements have twins that are other sides of the coin. Thus the first statement has a twin which reads like: When n-1 pigeons are to be put in n boxes, there is at least one box which remains empty (and receives no pigeons). The reader should similarly find the statements corresponding to the other two. Finally, all such kinds are called Pigeonhole principle or the Box principle. It seems the Box principle also called the Dirichlet drawer principle was used by Dirichlet and we will soon see the use of this principle as a non-trivial application to Diophantine approximations. Since the topic at an elementary level has much less by way of theory, we will give a few interesting examples in the next few blogs.

More later,

Nalin Pithwa



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s