Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

JUN  27  2022  MATH  175

3 . 1 The Pigeonhole Principle

Theorem.  If n + 1 objects are distributed into n boxes, then at least one box contains two or more of the objects .

Theorem.  Let q1 , q2 , · · · , qn   be positive integers .  If

q1  + q2  + · · · + qn  − n + 1

objects are distributed into n boxes, then either the first box contains at least q1  objects, or the second box contains at least q2   objects, . . ., or the nth box contains at least qn   objects .

Example (Page 82 # 9).  In a room there are 10 people, none of whom are older than 60 (ages are given in whole numbers only) but each of whom is at least 1 year old.  Prove that we can always find two groups of people  (with no common person) the sum of whose ages is the same .  Can 10 be replaced by a smaller number?

Solution.  First, without loss of generality, we may assume that these  10 people they all have different ages.  We can compute the number of groups of people, there are 210  − 1 = 1023 number of groups of people.  The number is obtained due to the fact that each person can either be in a group or not in a group, so there are 210  − 1 possibilities by excluding the case that no one is in this group.

On the other hand, the sum of age of a group ranges from 1+2+ · · · +10 = 55 to 60+59+ · · · +51 = 555. This gives there are 555 − 55 + 1 = 501 possibilities of sum of age.  So there are 1023 groups distributed into 501 possibilities, by the Pigeonhole principle, at least two groups will have the same sum of age. By excluding the common persons of these two groups, we find two groups of people (with no common person) the sum of whose ages is the same.

Last, we show that 10 can be replaced by 9 using the same method.  There are 29  − 1 = 511 number of groups of people and there are (52 + · · · + 60) − (1 + · · · + 9) + 1 = 460 possibilities of sum of age.  By the Pigeonhole principle, at least two groups will have the same sum of age.  By excluding the common persons of these two groups, we find two groups of people (with no common person) the sum of whose

ages is the same.                                                                                                                                                                     □