Generalized Pigeonhole Principle — Basic Applications

1) If 25 objects are placed into 6 boxes, what is the minimum number of objects guaranteed in one box?

3

4

5

6

⌈25/6⌉=⌈4.166...⌉=5\lceil 25/6 \rceil = \lceil 4.166...\rceil = 5⌈25/6⌉=⌈4.166...⌉=5

Explanation

⌈25/6⌉=⌈4.166...⌉=5\lceil 25/6 \rceil = \lceil 4.166...\rceil = 5⌈25/6⌉=⌈4.166...⌉=5

2) If 50 pencils are distributed among 8 drawers, what is the least number guaranteed in one drawer?

7

6

8

9

⌈50/8⌉=⌈6.25⌉=7\lceil 50/8 \rceil = \lceil 6.25 \rceil = 7⌈50/8⌉=⌈6.25⌉=7

Explanation

⌈50/8⌉=⌈6.25⌉=7\lceil 50/8 \rceil = \lceil 6.25 \rceil = 7⌈50/8⌉=⌈6.25⌉=7

3) What is the minimum number of students needed to guarantee at least 5 students are in the same group, if there are 7 groups?

28

29

30

35

We need nnn such that ⌈n/7⌉=5\lceil n/7 \rceil = 5⌈n/7⌉=5 → n=7×(5−1)+1=29n = 7×(5−1)+1 = 29n=7×(5−1)+1=29

Explanation

We need nnn such that ⌈n/7⌉=5\lceil n/7 \rceil = 5⌈n/7⌉=5 → n=7×(5−1)+1=29n = 7×(5−1)+1 = 29n=7×(5−1)+1=29

4) If 100 marbles are placed into 9 jars, the minimum number in one jar is

12

11

13

10

⌈100/9⌉=⌈11.11...⌉=12\lceil 100/9 \rceil = \lceil 11.11... \rceil = 12⌈100/9⌉=⌈11.11...⌉=12

Explanation

⌈100/9⌉=⌈11.11...⌉=12\lceil 100/9 \rceil = \lceil 11.11... \rceil = 12⌈100/9⌉=⌈11.11...⌉=12

5) How many socks must you pick from a drawer containing 4 colors to guarantee at least 6 of the same color?

21

20

18

19

Use n=k(m−1)+1=4(6−1)+1=21n = k(m-1)+1 = 4(6−1)+1 = 21n=k(m−1)+1=4(6−1)+1=21

Explanation

Use n=k(m−1)+1=4(6−1)+1=21n = k(m-1)+1 = 4(6−1)+1 = 21n=k(m−1)+1=4(6−1)+1=21

6) 73 balls are distributed among 12 bins. Minimum balls in one bin?

6

7

8

9

⌈73/12⌉=⌈6.08...⌉=7\lceil 73/12 \rceil = \lceil 6.08... \rceil = 7⌈73/12⌉=⌈6.08...⌉=7

Explanation

⌈73/12⌉=⌈6.08...⌉=7\lceil 73/12 \rceil = \lceil 6.08... \rceil = 7⌈73/12⌉=⌈6.08...⌉=7

7) For 15 objects and 4 boxes, what is the minimum number guaranteed in one box?

3

6

5

4

⌈15/4⌉=4\lceil 15/4 \rceil = 4⌈15/4⌉=4

Explanation

⌈15/4⌉=4\lceil 15/4 \rceil = 4⌈15/4⌉=4

8) How many people must be in a room to guarantee at least 9 share a birthday month?

96

97

100

110

n=12(9−1)+1=97n = 12(9−1)+1 = 97n=12(9−1)+1=97

Explanation

n=12(9−1)+1=97n = 12(9−1)+1 = 97n=12(9−1)+1=97

9) If 90 papers are placed in 11 folders, minimum in one folder is

8

10

7

9

⌈90/11⌉=⌈8.18...⌉=9\lceil 90/11 \rceil = \lceil 8.18...\rceil = 9⌈90/11⌉=⌈8.18...⌉=9

Explanation

⌈90/11⌉=⌈8.18...⌉=9\lceil 90/11 \rceil = \lceil 8.18...\rceil = 9⌈90/11⌉=⌈8.18...⌉=9

10) For 37 objects and 5 boxes, what’s the minimum guaranteed in one box?

8

7

9

6

⌈37/5⌉=⌈7.4⌉=8\lceil 37/5 \rceil = \lceil 7.4 \rceil = 8⌈37/5⌉=⌈7.4⌉=8

Explanation

⌈37/5⌉=⌈7.4⌉=8\lceil 37/5 \rceil = \lceil 7.4 \rceil = 8⌈37/5⌉=⌈7.4⌉=8