Channels ▼

Mark Nelson

Dr. Dobb's Bloggers

The Pigeonhole Principle

July 30, 2010

The Pigeonhole Principle, also referred to as the Counting Theorem, is a handy tool for mathematicians, and naturally, computer programmers.

The loose version of this principle says "After placing n pigeons into m compartments, if n is greater than m, you will find that some compartment must contain more than one pigeon."

Seems obvious, and perhaps it is, but at least in the world of data compression it must be trotted out from time to time in order to bludgeon dreams back to reality.

Impossible Compression

A common dream for the novice is the creation of a compressor that will reduce the size of all files. (Often touted as the ability to compress "random" data.) For example, Dr. Constant Wong of Recursiveware has been polishing his technique for compressing random data since 2003. And the USENET newsgroup comp.compression always has at least one thread dedicated to thrashing a new and eager theorist with a (flawed) idea.

The Pigeonhole Principle quickly puts this idea to rest. We know that if a file is of length n bits, there are 2n possible input files. If a compressor can reduce the size of every file, the number of possible output files is 2n-1. The Pigeonhole Principle tells us that the output of at least two file compressions have to be identical. And since they are identical, the decompressor cannot create two different output files.

And More

The Wikipedia has another nice example of the principle in use. Imagine that you have a party with n people attending. At random, people shake hands with one another as they mill about. At the end of the night, we check the number of unique individuals each person has shaken with. What are the odds that two people will have shaken hands with the same number of people?

The answer is of course that there will always be two people who have shaken the same number of hands. There are n-1 pigeonholes, and n pigeons, QED.

Don't Go There

If you ever find yourself spiraling down the rabbit hole of impossible data compression, I urge you to grab the life jacket of the Pigeon Principle before you are lost. It will save you a lot of pointless effort, plus clue you in to the fact that there are two IBM employees with the same number of hairs on their head.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video