The pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item.
A function from one finite set to a smaller finite set cannot be one-to-one.
Prove that one selects 55 integers 1 ≤ x1 < x2 < x3 < ... < x55 ≤ 100, there will be some two that differ by 9. ___________
Answer:
Given a run of 2n consecutive integers: a + 1, a + 2, ..., a + 2n - 1, a + 2n, there are n pairs of numbers that differ by n: (a+1, a+n+1), (a + 2, a + n + 2), ..., (a + n, a + 2n). Therefore, by the Pigeonhole Principle, if one selects more than n numbers from the set, two are liable to belong to the same pair that differ by n.
Given a run of 2n consecutive integers: a + 1, a + 2, ..., a + 2n - 1, a + 2n, there are n pairs of numbers that differ by n: (a+1, a+n+1), (a + 2, a + n + 2), ..., (a + n, a + 2n). Therefore, by the Pigeonhole Principle, if one selects more than n numbers from the set, two are liable to belong to the same pair that differ by n.