Pigeonhole Principle Foundations Quiz

1) If 13 people are in a room, what is the minimum number who must share a birth month?

1

2

3

12

13 people, 12 months → at least 2 must share.

Explanation

13 people, 12 months → at least 2 must share.

2) The Pigeonhole Principle states: if nobjects are placed into kboxes and n>k, then at least one box contains more than one object.

True

False

Basic pigeonhole principle.

Explanation

Basic pigeonhole principle.

3) What is the minimum number of socks you must draw from a drawer containing 6 blue, 6 black, and 6 white socks to guarantee a matching pair?

2

3

4

5

Worst-case pick one of each color; 4th ensures match.

Explanation

Worst-case pick one of each color; 4th ensures match.

4) If 51 integers are chosen from the set {1, 2, 3, …, 100}, what must be true?

At least two numbers differ by 10

At least two numbers are consecutive

At least two numbers are the same

At least two numbers have the same remainder mod 50

50 remainder classes → 51 numbers guarantee a repeat.

Explanation

50 remainder classes → 51 numbers guarantee a repeat.

5) The generalized pigeonhole principle states: if n objects are placed into k boxes, then some box must contain at least ⌈n/k⌉objects.

True

False

This is the generalized principle.

Explanation

This is the generalized principle.

6) In any group of 6 people, there must be at least:

2 who have the same number of friends within the group

3 who are mutual friends

3 who are mutual strangers

Both b and c

Friend counts range from 0 to 5, but 0 and 5 cannot occur together → two must match.

Explanation

Friend counts range from 0 to 5, but 0 and 5 cannot occur together → two must match.

7) Which situations guarantee the use of the pigeonhole principle?

Ensuring duplication among more items than categories

Ensuring a hand of cards contains certain suits

Ensuring collisions in hashing

Ensuring two people have the same number of hairs

These rely on more items than bins → duplication guaranteed.

Explanation

These rely on more items than bins → duplication guaranteed.

Submit

8) How many numbers must be selected from {1, 2, …, 30} to guarantee that two selected numbers sum to 31?

2

12

16

17

15 complementary pairs → selecting 16 forces a repeated pair.

Explanation

15 complementary pairs → selecting 16 forces a repeated pair.

9) A drawer has 8 pairs of shoes mixed together. What is the minimum number of shoes you must pick to guarantee a matching pair?

9

10

8

16

Worst case take 8 left shoes; 9th must match.

Explanation

Worst case take 8 left shoes; 9th must match.

10) If 20 pigeons enter 19 pigeonholes, at least one pigeonhole contains at least two pigeons.

True

False

More pigeons than holes → at least one hole gets ≥2.

Explanation

More pigeons than holes → at least one hole gets ≥2.

11) Match each concept to its description:

Basic pigeonhole principle

Generalized pigeonhole principle

Pigeonhole application

Pigeonhole counterexample

Definitions match directly.

Explanation

Definitions match directly.

Submit

12) How many numbers do you need to select from {1, 2, …, 100} to guarantee two have the same remainder when divided by 9?

9

10

11

12

9 possible remainders → 10 numbers force a repeat.

Explanation

9 possible remainders → 10 numbers force a repeat.

13) If a function maps a larger finite set into a smaller finite set, it must be injective.

True

False

Impossible—must have collisions.

Explanation

Impossible—must have collisions.

14) Seven points are placed inside a 2×2 square. Which statement is guaranteed?

Two points are at most √2 apart

Two points lie within one of four 1×1 subsquares

All points lie on the boundary

No two points can share an x-coordinate

4 subsquares → 7 points → one must hold ≥2.

Explanation

4 subsquares → 7 points → one must hold ≥2.

15) If 100 integers are selected, which statements must be true?

Two share a remainder mod 5

Two share a remainder mod 10

Two are multiples of the same number

Two differ by a multiple of 9

5 and 10 remainder classes → must repeat with 100 numbers.

Explanation

5 and 10 remainder classes → must repeat with 100 numbers.

Submit

Pigeonhole Principle Foundations Quiz

What do you like, dislike, and how can we improve?