Thue used this result in order to prove the existence of auxiliary function as part of his proof of Siegel's lemma, (*) while applying it to the first 2N positive integers is used to prove Proizvolov's identity.
This result names a complexity class whose central problem asks whether a function that takes n-bit strings to each other can return a string of all zeros or two inputs map to the same output, while Rhodes showed that this result has Chvatal Rank O(Log n). Thue used this result in order to prove the existence of auxiliary function as part of his proof of Siegel's lemma, (*) while applying it to the first 2N positive integers is used to prove Proizvolov's identity. This result can be used to show that for an irrational number q, the fractional parts generated by multiplying it by the set of integers are dense in [0, 1]. It can also be used to show that collisions in a hash table are inevitable, that two people in a party of n have the same number of friends present, and that at least two of any group of 3 people shares a gender. For 10 points, name this combinatorial principle that states if n+1 objects are placed in n boxes, one box has to have two items.
This result names a complexity class whose central problem asks whether a function that takes n-bit strings to each other can return a string of all zeros or two inputs map to the same output, while Rhodes showed that this result has Chvatal Rank O(Log n).
{Pigeonhole} Principle [or {Dirichlet's} Box Principle]