Editing Pigeonhole principle (section)

== Uses and applications ==
The principle can be used to prove that any [[lossless compression]] algorithm, provided it makes some inputs smaller (as "compression" suggests), will also make some other inputs larger. Otherwise, the set of all input sequences up to a given length {{mvar|L}} could be mapped to the (much) smaller set of all sequences of length less than {{mvar|L}} without collisions (because the compression is lossless), a possibility that the pigeonhole principle excludes.

[[File:Dudeney_no_3_pawns_in_line.svg|thumb|The pigeonhole principle gives an upper bound of {{math|2''n''}} in the ''[[no-three-in-line problem]]'' for the number of points that can be placed on an {{math|''n'' &times; ''n''}} lattice without any three being colinear &ndash; in this case, 16 pawns on a regular chessboard&thinsp;<ref>{{cite magazine
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | date = October 1976
 | department = Mathematical Games
 | issue = 4
 | magazine = [[Scientific American]]
 | jstor = 24950467
 | pages = 131–137
 | title = Combinatorial problems, some old, some new and all newly attacked by computer
 | volume = 235}}</ref>]]

A notable problem in [[mathematical analysis]] is, for a fixed [[irrational number]] {{mvar|a}}, to show that the set {{tmath|\{[na]: n \in \Z \} }} of [[fractional part]]s is [[Dense-in-itself|dense]] in {{math|[0, 1]}}. One finds that it is not easy to explicitly find integers {{mvar|n, m}} such that <math>|na-m| < e,</math> where {{math|''e'' > 0}} is a small positive number and {{mvar|a}} is some arbitrary irrational number. But if one takes {{mvar|M}} such that {{tmath|\tfrac 1 M < e,}} by the pigeonhole principle there must be <math>n_1, n_2 \in \{1, 2, \ldots, M+1\}</math> such that {{math|''n''<sub>1</sub>''a''}} and {{math|''n''<sub>2</sub>''a''}} are in the same integer subdivision of size {{tmath|\tfrac 1 M}} (there are only {{mvar|M}} such subdivisions between consecutive integers). In particular, one can find {{math|''n''<sub>1</sub>, ''n''<sub>2</sub>}} such that
:<math>n_1 a \in \left(p+\frac k M,\ p + \frac{k+1}{M}\right), \quad n_2 a \in \left(q+ \frac k M,\ q+\frac{k+1}{M}\right),</math>
for some {{mvar|p, q}} integers and {{mvar|k}} in {{math|{0, 1, ..., ''M'' &minus; 1}}}. One can then easily verify that 
:<math>(n_2 - n_1)a \in \left(q-p-\frac 1 M, q-p+\frac 1 M \right).</math>
This implies that {{tmath|[na] < \tfrac 1 M < e,}} where {{math|1=''n'' = ''n''<sub>2</sub> &minus; ''n''<sub>1</sub>}} or {{math|1=''n'' = ''n''<sub>1</sub> &minus; ''n''<sub>2</sub>}}. This shows that 0 is a limit point of {[{{math|''na''}}]}. One can then use this fact to prove the case for {{mvar|p}} in {{math|(0, 1]}}: find {{mvar|n}} such that {{tmath|[na] < \tfrac 1 M < e;}} then if {{tmath|p \in \bigl(0, \tfrac 1 M \bigr],}} the proof is complete. Otherwise 
:<math>p \in \left(\frac j M, \frac{j+1}{M}\right],</math>
and by setting 
:<math>k = \sup \left\{r \in N : r[na] < \frac j M \right\},</math> 
one obtains 
:<math>\Bigl| \bigl[ (k+1)na \bigr] - p \Bigr| < \frac 1 M < e.</math>

Variants occur in a number of proofs. In the proof of the [[pumping lemma for regular languages]], a version that mixes finite and infinite sets is used: If infinitely many objects are placed into finitely many boxes, then two objects share a box.<ref>''Introduction to Formal Languages and Automata'', Peter Linz, pp.&nbsp;115–116, Jones and Bartlett Learning, 2006</ref> In Fisk's solution to the [[Art gallery problem]] a sort of converse is used: If {{mvar|n}} objects are placed into {{mvar|k}} boxes, then there is a box containing at most {{tmath|\tfrac n k}} objects.<ref>''Computational Geometry in C'',  Cambridge Tracts in Theoretical Computer Science, 2nd Edition, Joseph O'Rourke, page 9.</ref>