Pigeonhole Principle Quiz: Fundamental Pigeonhole Statement

1) Place 11 balls into 10 boxes. What is the least number you can guarantee in some box?

1

2

3

10

Use the pigeonhole principle with k=11 objects and n=10 boxes. Guaranteed maximum occupancy is at least ⌈11/10⌉ = 2, so some box has at least 2 balls.

Explanation

Use the pigeonhole principle with k=11 objects and n=10 boxes. Guaranteed maximum occupancy is at least ⌈11/10⌉ = 2, so some box has at least 2 balls.

2) Distributing n+1 objects into n boxes guarantees some box contains at least two objects.

True

False

By the fundamental pigeonhole principle, k>n implies at least one box has ≥2 objects.

Explanation

By the fundamental pigeonhole principle, k>n implies at least one box has ≥2 objects.

3) With 37 students and 12 birth months, at least ____ students share a birth month.

Compute ⌈37/12⌉. Since 12×3=36 and 37>36, ⌈37/12⌉=4, so some month has at least 4 students.

Explanation

Compute ⌈37/12⌉. Since 12×3=36 and 37>36, ⌈37/12⌉=4, so some month has at least 4 students.

Submit

4) Among 100 people, must two share the same first initial (26 letters)?

Yes, because 100>26

No, because 100<26×4

No, because initials can all be different

Yes, but only if 100≥52

There are 26 initial boxes. Since 100>26, by the pigeonhole principle at least two people share the same initial.

Explanation

There are 26 initial boxes. Since 100>26, by the pigeonhole principle at least two people share the same initial.

5) Which scenarios guarantee a repeat by the pigeonhole principle? Select all that apply.

Choose 51 integers; two share the same remainder mod 50

Choose 12 people; two share a birth month

Choose 367 people; two share a birthday (365-day year)

Choose 10 socks from 9 colors; two share a color

Choose 26 words; two start with the same letter

A: 51 into 50 remainder boxes ⇒ repeat. C: 367 into 365 days ⇒ repeat. D: 10 into 9 colors ⇒ repeat. B and E each put n items into n boxes, which does not force a repeat.

Explanation

A: 51 into 50 remainder boxes ⇒ repeat. C: 367 into 365 days ⇒ repeat. D: 10 into 9 colors ⇒ repeat. B and E each put n items into n boxes, which does not force a repeat.

Submit

6) Minimum people needed to ensure at least 3 share the same first initial (26 letters)?

52

53

54

55

To force 3 in one box among 26 letters, need 2·26+1=53 (pigeonhole with threshold m=3: (m−1)n+1).

Explanation

To force 3 in one box among 26 letters, need 2·26+1=53 (pigeonhole with threshold m=3: (m−1)n+1).

7) With 20 pigeons and 6 holes, some hole must contain at least 4 pigeons.

True

False

⌈20/6⌉=⌈3.33…⌉=4, so at least one hole has ≥4 pigeons.

Explanation

⌈20/6⌉=⌈3.33…⌉=4, so at least one hole has ≥4 pigeons.

Submit

9) Place 100 balls into 33 boxes. What is the least guaranteed maximum in some box?

2

3

4

5

Compute ⌈100/33⌉. Since 33·3=99 and 100>99, ⌈100/33⌉=4; some box has at least 4 balls.

Explanation

Compute ⌈100/33⌉. Since 33·3=99 and 100>99, ⌈100/33⌉=4; some box has at least 4 balls.

10) Select all correct general statements.

If k objects go into n boxes, some box has at least ⌈k/n⌉ objects

If k>n(m−1), some box has at least m objects

If k=n(m−1), some box has at least m objects

If k=n, duplication is guaranteed

If k≤n, then no box can have more than 1 object

A is the averaging form. B is the threshold form. C is false (all boxes could have m−1). D is false (could be one per box). E is not guaranteed; k≤n allows but does not force ≤1 per box.

Explanation

A is the averaging form. B is the threshold form. C is false (all boxes could have m−1). D is false (could be one per box). E is not guaranteed; k≤n allows but does not force ≤1 per box.

Submit

11) Choosing 10 integers from 1–18 guarantees two differ by 9.

True

False

Partition 1–18 into 9 pairs {1,10},{2,11},…,{9,18}. With 10 picks, one pair must be chosen by PHP, giving a difference of 9.

Explanation

Partition 1–18 into 9 pairs {1,10},{2,11},…,{9,18}. With 10 picks, one pair must be chosen by PHP, giving a difference of 9.

12) Minimum people needed so two share the same last digit (0–9): ____

There are 10 possible last digits. With 11 people, by PHP two share a last digit.

Explanation

There are 10 possible last digits. With 11 people, by PHP two share a last digit.

Submit

13) From a drawer with many socks of only two colors, what is the fewest socks to guarantee at least two of the same color?

2

3

4

5

Two color boxes. Picking 3 socks forces one color to appear at least twice (⌈3/2⌉=2).

Explanation

Two color boxes. Picking 3 socks forces one color to appear at least twice (⌈3/2⌉=2).

14) Remainders modulo 4: which choices force two numbers with the same remainder?

Pick 5 integers (any)

Pick 4 integers (any)

Pick 13 integers (any)

Pick 8 integers (any)

Pick 3 integers (any)

There are 4 remainder boxes. A: 5>4 guarantees a match. C: 13>4 guarantees a match. B and D can be spread evenly; E is too few to force a repeat.

Explanation

There are 4 remainder boxes. A: 5>4 guarantees a match. C: 13>4 guarantees a match. B and D can be spread evenly; E is too few to force a repeat.

Submit

15) For any 7 integers, two have the same remainder when divided by 6.

True

False

There are 6 remainder classes mod 6. With 7 integers, one remainder repeats.

Explanation

There are 6 remainder classes mod 6. With 7 integers, one remainder repeats.

16) Smallest number of people needed to ensure two share a birth month: ____

There are 12 months; with 13 people, two share a month (n+1 into n).

Explanation

There are 12 months; with 13 people, two share a month (n+1 into n).

Submit

17) With 15 pigeons and 4 holes, the least guaranteed maximum in some hole is ____

3

4

5

6

Compute ⌈15/4⌉=⌈3.75⌉=4. So some hole has at least 4 pigeons.

Explanation

Compute ⌈15/4⌉=⌈3.75⌉=4. So some hole has at least 4 pigeons.

18) Which statements are always true when placing k objects into n boxes?

At least one box has ≥⌈k/n⌉ objects

At least one box has ≤⌊k/n⌋ objects

Every box has exactly ⌈k/n⌉ objects

Every box has at least ⌈k/n⌉ objects

Every box has at most ⌊k/n⌋ objects

By averaging, some box meets or exceeds the ceiling, and some meets or is below the floor. The universal statements C–E are not guaranteed.

Explanation

By averaging, some box meets or exceeds the ceiling, and some meets or is below the floor. The universal statements C–E are not guaranteed.

Submit

19) Choosing 100 integers from 1–200 guarantees two sum to 201.

True

False

Partition into 100 complement pairs (1,200),(2,199),…,(100,101). With 100 picks you could take one from each pair; 101 are needed to force a complementary pair.

Explanation

Partition into 100 complement pairs (1,200),(2,199),…,(100,101). With 100 picks you could take one from each pair; 101 are needed to force a complementary pair.

20) Smallest number n so that placing n objects into 10 boxes guarantees some box has at least 12 objects: ____

Use (m−1)n+1 with m=12, n=10: (12−1)·10+1=110+1=111.

Explanation

Use (m−1)n+1 with m=12, n=10: (12−1)·10+1=110+1=111.

Submit