The Pigeonhole Principle

I am a self-avowed fan of mathematics, numbers in particular. I might use it tangentially in my life these days but the epiphanic moments when I understand a new idea, especially a concept that is neat and elegant, are something I cherish.

So, my most recent discovery has been the Pigeonhole Principle. As always, Wikipedia does a great job of explaining it, along with its applications, variations and generalisations. I especially like this one because it seems to be so blatantly obvious – if you need to fit n pigeons in holes (where n>m, like, say 4 pigeons in 3 holes), then at least one hole will have more than one pigeon in it – but it is deceptive in its simplicity.

It can be used to solve interesting riddles like the ‘number of people with the exact number of hair in London’. But, as you will learn from the Wiki article, it is also used to prove tenets of lossless compression algorithms and in linguistics, to prove language lemmas ( a supporting theorem).

Simple and elegant.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.