Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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