Most of the problems I've seen involving the pigeonhole principle have so far seemed fairly artificial. As I'm studying CompSci I'm interested what kind of practical, real world problems in CompSci are solved using this principle?

  • $\begingroup$ @Stefan That's already included in the accepted answer, albeit without the link. $\endgroup$ – Robert S. Barnes Jan 25 '15 at 14:05
  • $\begingroup$ For sure, sorry, I deleted my comment. $\endgroup$ – StefanH Jan 25 '15 at 14:20

Some problems can be shown not to be solvable using the pigeonhole principle. For example, the nonexistence of a universal lossless compression algorithm (an algorithm that always compresses a string of characters into a shorter string of characters) can be shown to be impossible by using a pigeonhole argument that shows that two strings would have to be compressed into the same compressed representation, making it impossible to losslessly decompress the string. The pigeonhole principle is also the basis for the pumping lemma for regular and context-free languages, which can be used to show that certain languages are not regular or context-free. These proofs are a bit more involved, but can be used to show that programming languages can't be parsed purely by regular expressions and context-free grammars.

The pigeonhole principle can be used in a more subtle way to derive the $\Omega(n \log n)$ lower bound on comparison sorts by showing that if the algorithm makes fewer comparisons than this, there must be some pair of inputs that the algorithm wouldn't be able to distinguish, since there are more possible inputs than configurations of the algorithm. Similar arguments can be used to show other lower bounds in other problems.

Also in CS theory, the proof that the word problem for linear bounded automata (that is, given an LBA and a string, does the LBA accept the string?) can be shown to be decidable using the pigeonhole principle. You just watch the automata for some number of steps, and if it ever enters a duplicate configuration, it must loop forever. Since there are only finitely many configurations of the LBA when run on a given input string w (say there are n possible configurations) this process is guaranteed to terminate in at most n + 1 steps, since after n + 1 the machine must either have halted or visited some state twice and is looping infinitely.

Hope this helps!

  • 1
    $\begingroup$ "The pigeonhole principle can be used in a more subtle way to derive the Ω(nlogn) lower bound on comparison sorts by showing that...." Sounds interesting ! I would love to read a detailed proof for that particular point. Would you have references ? $\endgroup$ – Adren May 1 '18 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.