Pigeonhole Principle: Theory, Logic, and Applications Quiz

1) The basic pigeonhole principle states that if objects are placed into boxes and , then:

All boxes must be full

At least one box contains ≥ 2 objects

Each box contains the same number

Some boxes must be empty

More objects than boxes forces at least one box to contain ≥2.

Explanation

More objects than boxes forces at least one box to contain ≥2.

2) The generalized pigeonhole principle says some box contains at least objects.

True

False

It states some box has at least ⌈n/k⌉ objects.

Explanation

It states some box has at least ⌈n/k⌉ objects.

3) If 32 items are placed into 7 bins, the minimum number guaranteed in one bin is:

4

5

6

7

⌈32/7⌉ = 5.

Explanation

⌈32/7⌉ = 5.

4) A “pigeon” refers to:

A box

A category

An object being placed

A remainder

In the principle, pigeons = objects.

Explanation

In the principle, pigeons = objects.

5) A “pigeonhole” refers to:

An object

A container or category

A pattern

A probability

Pigeonholes = boxes/categories receiving objects.

Explanation

Pigeonholes = boxes/categories receiving objects.

6) You can apply the pigeonhole principle to infinite sets without modification.

True

False

The classical form assumes finite sets.

Explanation

The classical form assumes finite sets.

7) If you place 10 integers into 3 residue classes modulo 3, at least one class contains at least:

3

4

5

10

⌈10/3⌉ = 4.

Explanation

⌈10/3⌉ = 4.

8) Which situations naturally use the pigeonhole principle?

Ensuring repeated birthdays

Guaranteeing matching socks

Proving two numbers share a remainder

Computing limits

All involve more items than categories → forced repetition.

Explanation

All involve more items than categories → forced repetition.

Submit

9) If 20 people each pick a number from 1 to 15, then at least two people choose:

The same number

A number of the same parity

Consecutive numbers

None of the above

20 > 15 → two must pick the same number.

Explanation

20 > 15 → two must pick the same number.

10) If you distribute items among boxes, then the average number per box is .

True

False

Average = total objects ÷ total boxes.

Explanation

Average = total objects ÷ total boxes.

11) If 17 exam papers are placed into 4 folders, one folder has at least:

3

5

4

7

⌈17/4⌉ = 5.

Explanation

⌈17/4⌉ = 5.

12) The pigeonhole principle is often used to prove existence, not to construct specific examples.

True

False

It is a non-constructive proof method.

Explanation

It is a non-constructive proof method.

13) A collision in hashing terminology corresponds to:

Empty buckets

Duplicate keys

Two items in the same bucket

Deleting an entry

A collision occurs when multiple items hash to one location.

Explanation

A collision occurs when multiple items hash to one location.

14) Which statements characterize the pigeonhole principle?

Forces repetition

Guarantees surjectivity

Used to show impossibility

Applies to categories of outcomes

It forces duplication and applies to categorized outcomes.

Explanation

It forces duplication and applies to categorized outcomes.

Submit

15) You choose 50 integers from the set . What must be true?

Two differ by at most 1

Two have the same remainder when divided by 45

Two are both prime

None of the above

45 remainder classes → 50 choices guarantee a repeat.

Explanation

45 remainder classes → 50 choices guarantee a repeat.

Pigeonhole Principle: Theory, Logic, and Applications Quiz

1) The basic pigeonhole principle states that if objects are placed into boxes and , then:

2)

What first name or nickname would you like us to use?

2) The generalized pigeonhole principle says some box contains at least objects.

3) If 32 items are placed into 7 bins, the minimum number guaranteed in one bin is:

4) A “pigeon” refers to:

5) A “pigeonhole” refers to:

6) You can apply the pigeonhole principle to infinite sets without modification.

7) If you place 10 integers into 3 residue classes modulo 3, at least one class contains at least:

8) Which situations naturally use the pigeonhole principle?

9) If 20 people each pick a number from 1 to 15, then at least two people choose:

10) If you distribute items among boxes, then the average number per box is .

11) If 17 exam papers are placed into 4 folders, one folder has at least:

12) The pigeonhole principle is often used to prove existence, not to construct specific examples.

13) A collision in hashing terminology corresponds to:

14) Which statements characterize the pigeonhole principle?

15) You choose 50 integers from the set . What must be true?