Pigeonhole Principle Quiz: Fundamental Pigeonhole Statement

The answer is True. Partition 1 to 18 into 9 pairs: {1,10}, {2,11}, {3,12}, {4,13}, {5,14}, {6,15}, {7,16}, {8,17}, {9,18}. Each pair has a difference of 9. With 10 integers chosen from 9 pairs, by the pigeonhole principle two must come from the same pair, giving a difference of exactly 9.

Use (m-1) times n + 1 with m=12 and n=10: (12-1) times 10 + 1 = 110 + 1 = 111. With 110 objects, distributing exactly 11 per box is possible. The 111th object forces some box to reach 12. Option A gives 101 = (10-1) times 10 + 1 + something, too small. Option B gives 105, option C gives 110, both of which allow all boxes to hold at most 11.

The answer is False. Partition 1 to 200 into 100 complement pairs: {1,200}, {2,199}, ..., {100,101}. With exactly 100 integers chosen, it is possible to select one number from each pair, avoiding any pair that sums to 201. Only with 101 integers would the pigeonhole principle force two numbers from the same pair, guaranteeing a sum of 201.

By the averaging argument, if some box exceeded ⌈k/n⌉ another must fall below the average, confirming both A and B. Option C is false — uniform distribution only occurs when k is divisible by n. Option D is false — only some box is guaranteed to reach the ceiling, not every box.

⌈15/4⌉ = ⌈3.75⌉ = 4. If every hole held at most 3 pigeons, the total capacity would be 4 times 3 = 12, which is less than 15. Therefore at least one hole must contain 4 or more pigeons. Option A gives 3, which is insufficient. Options C and D cannot be guaranteed with only 15 pigeons.

There are 12 months. With 12 people, it is possible for each to have a different birth month. The 13th person must share a month with someone already present. This is the fundamental n+1 into n form of the pigeonhole principle with n=12. Options A and B are insufficient. Option D exceeds the minimum needed.

The answer is True. Division by 6 produces exactly 6 possible remainders: 0, 1, 2, 3, 4, and 5. With 7 integers distributed among 6 remainder classes, by the pigeonhole principle at least two must share the same remainder.

There are 4 remainder classes mod 4. Option A: 5 exceeds 4, forcing a repeated remainder, confirming A. Option C: 13 exceeds 4, also forcing a repeat, confirming C. Option B: picking exactly 4 integers allows one per remainder class with no forced repeat. Option D: 3 is less than 4, so all three could have different remainders.

With 2 colors, picking 2 socks could give one of each color. The 3rd sock must match one of the two already drawn. So ⌈3/2⌉ = 2 objects in some color box is guaranteed with 3 picks. Option A gives 2, which could yield one of each color with no guarantee of a match. Options C and D exceed the minimum needed.

There are 10 possible last digits (0 through 9). With 10 people, it is possible for each to have a different last digit. The 11th person must share a last digit with someone already present. Option A gives 9, which is too few. Option B gives 10, which allows one person per digit with no forced repeat. Option D gives 12, which exceeds the minimum needed.

By the pigeonhole principle, ⌈11/10⌉ = 2. If 11 balls are distributed among 10 boxes, at least one box must contain 2 or more balls. Option A gives 1, which is too weak — we can guarantee more than 1. Option C gives 3, which is too strong since 11 balls could be spread as ten boxes with 1 and one with 2. Option D gives 10, which is impossible to guarantee.

Option A is the averaging form of the pigeonhole principle, always true, confirming A. Option B is the threshold form: if k exceeds n(m-1), some box must reach m, confirming B. Option C is false — if k = n(m-1), distributing exactly m-1 to each box is possible with no box reaching m. Option D is false — k=n allows exactly one object per box with no duplication.

⌈100/33⌉ = 4 since 33 times 3 = 99 and 100 exceeds 99. At least one box must contain 4 or more balls. Option A gives 2, too weak. Option B gives 3, which would require only 99 balls to force. Option D gives 5, which cannot be guaranteed with 100 balls in 33 boxes since 33 times 4 = 132 exceeds 100.

Use (m-1) times n + 1 with m=5 and n=7: (5-1) times 7 + 1 = 28 + 1 = 29. With 28 students, it is possible to have exactly 4 per weekday. The 29th student forces some weekday to reach 5. Option A gives 25, option B gives 27, option D gives 31, none of which correctly apply the threshold formula.

The answer is True. ⌈20/6⌉ = ⌈3.333...⌉ = 4. Distributing 20 pigeons into 6 holes, if every hole held at most 3 the total capacity would be 6 times 3 = 18, which is less than 20. Therefore at least one hole must contain 4 or more pigeons.

Use the formula (m-1) times n + 1 with m=3 and n=26: (3-1) times 26 + 1 = 52 + 1 = 53. With 52 people, it is possible to have exactly 2 per initial with no initial having 3. The 53rd person must go into an initial already containing 2, guaranteeing a third. Option A gives 52, which only guarantees 2 per initial. Options C and D exceed the minimum needed.

Option A: 51 objects into 50 remainder boxes, 51 > 50, guarantees a repeat, confirming A. Option C: 367 people into 365 days, 367 > 365, guarantees a repeat, confirming C. Option D: 10 socks into 9 colors, 10 > 9, guarantees a repeat, confirming D. Option B: 12 people into 12 months places exactly one person per month with no forced repeat.

With 26 possible initials and 100 people, since 100 exceeds 26, by the pigeonhole principle at least two people must share the same initial. Option B is false — the comparison to 26 times 4 is irrelevant. Option C is false — with more people than boxes repetition is forced. Option D is false — the condition requires only that people exceed boxes, which 100 does over 26.

⌈37/12⌉ = 4 since 12 times 3 = 36 and 37 exceeds 36. At least one month must contain 4 or more students. Option A gives 3, which underestimates — with 37 students in 12 months the ceiling is 4 not 3. Options C and D are too strong and cannot be guaranteed with only 37 students.

The answer is True. With n+1 objects and only n boxes, if every box held at most 1 object the total capacity would be at most n. But n+1 exceeds n, so at least one box must hold 2 or more objects. This is the fundamental statement of the pigeonhole principle.