Pigeonhole Example Quiz: Socks in a Drawer Pigeonhole

Using (m-1) times c + 1 with m=4 and c=5: (4-1) times 5 + 1 = 15 + 1 = 16. In the worst case 15 draws give exactly 3 of each color. The 16th draw must add a fourth to some color. Option A gives 12, option B gives 14, option D gives 18, none of which correctly apply the formula with m=4 and c=5.

There are 3 colors so the threshold is c+1 = 4. In the worst case draw one red, one blue, one green (3 draws, no pair). The 4th draw must match red or blue since all colors are still available, guaranteeing a pair. The green sock having only 1 does not change the threshold since all 3 colors are present. Option A gives 3, which allows one of each. Options C and D exceed the minimum.

The answer is False. Consider c=3 colors with many socks of each. Drawing 6 socks (2c with c=3) could yield 4 red and 1 blue and 1 green — one matching pair of red but no second pair from blue or green. The formula only guarantees at least one pair from c+1 draws, not two distinct pairs from 2c draws.

Option A is the general threshold formula, always correct, confirming A. Option B is the pair-specific case with m=2, always correct, confirming B. Option D is correct because absent colors only reduce the effective number of boxes, making the bound sufficient or more than sufficient. Option C is false — drawing exactly c socks allows one of each color with no pair forced.

Using (m-1) times c + 1 with m=3 and c=6: (3-1) times 6 + 1 = 12 + 1 = 13. In the worst case 12 draws give exactly 2 of each color. The 13th draw must add a third to some color. Option A gives 11, option B gives 12, option D gives 14, none of which correctly apply the formula with m=3 and c=6.

Using (m-1) times c + 1 with m=5 and c=3: (5-1) times 3 + 1 = 12 + 1 = 13. In the worst case 12 draws give exactly 4 of each color. The 13th draw must add a fifth to some color. Option A gives 11, option B gives 12, option D gives 14, none of which correctly apply the formula.

The answer is True. With c=2 colors, the threshold is c+1 = 3. In the worst case the first 2 draws yield one sock of each color. The 3rd draw must match one of the two colors already present, guaranteeing a pair. With only 2 color boxes, 3 items cannot all be in different boxes.

There are 3 colors so the threshold is c+1 = 4. In the worst case draw one red, one blue, one green (3 draws, no pair). The 4th draw must match one of the three colors already drawn, guaranteeing a pair. The exact counts per color do not matter as long as each color has at least one sock. Options B, C, and D exceed the minimum needed.

Using (m-1) times 4 + 1: m=2 gives (1) times 4 + 1 = 5, confirming A. m=3 gives (2) times 4 + 1 = 9, confirming C. m=4 gives (3) times 4 + 1 = 13, confirming D. Option B gives 4, which only equals the number of colors — with 4 draws one of each color is possible so no pair is guaranteed.

Using (m-1) times c + 1 with m=3 and c=4: (3-1) times 4 + 1 = 8 + 1 = 9. In the worst case 8 draws give exactly 2 of each color. The 9th draw must add a third to some color. Option A gives 7, option B gives 8, option D gives 10, none of which correctly apply the formula with m=3 and c=4.

Using the formula (m-1) times c + 1 with m=2 and c=3: (2-1) times 3 + 1 = 4. In the worst case the first 3 draws are one of each color with no pair. The 4th draw must match one of the three colors already drawn, guaranteeing a pair. Option A gives 3, which allows one of each color with no guarantee. Options C and D exceed the minimum needed.

The answer is True. The threshold for a pair with c=7 colors is c+1 = 8. In the worst case the first 7 draws are one of each color. The 8th draw must match one of the 7 colors already represented, guaranteeing a matching pair.

Option A: 8 exceeds 7, guaranteeing a repeated color, confirming A. Option B: 10 exceeds 3, guaranteeing a repeat, confirming B. Option D: 12 exceeds 11, guaranteeing a repeat, confirming D. Option C: 5 draws from 5 colors allows exactly one of each color with no pair — the number of draws equals the number of colors so no repeat is forced.

The guarantee depends on the number of distinct colors, not the sock counts, as long as each color is present. With 3 colors, the threshold is c+1 = 3+1 = 4. In the worst case one draw of each color gives 3 socks with no pair. The 4th must match a color already drawn. Option A gives 5, option B gives 6, both exceeding the minimum. Option C gives 3, which allows one of each color.

Using (m-1) times c + 1 with m=2 and c=6: (2-1) times 6 + 1 = 7. In the worst case the first 6 draws are one of each color. The 7th draw must match one already drawn. Option B gives 6, which allows one of each color with no forced pair. Options A and D are either too few or exceed the minimum needed.

The answer is True. There are 3 colors, so the threshold for a pair is c+1 = 4. In the worst case the first 3 draws yield one of each color with no pair. Since there are at least 2 socks of each color, the 4th draw must match one of the three colors already drawn, guaranteeing a pair.

The worst case is drawing exactly m-1 socks of each color, giving (m-1) times c total. The very next draw forces some color to reach m, so the threshold is (m-1) times c + 1, confirming A. Option B gives c+m, which is insufficient for large m. Option C gives c times m, which is too large for m=2 and insufficient for other combinations. Option D reduces c by 1, producing an incorrect lower bound that does not account for all colors.

Using (m-1) times c + 1 with m=3 and c=5: (3-1) times 5 + 1 = 10 + 1 = 11. In the worst case 10 draws give exactly 2 of each color. The 11th draw must add a third to some color. Option B gives 9, too few. Options A and D give 10 and 12, neither of which correctly apply the formula.

Using (m-1) times c + 1 with m=2 and c=4: (2-1) times 4 + 1 = 5. In the worst case the first 4 draws are one of each color. The 5th draw must match one already drawn. Option B gives 4, which allows one of each color with no forced pair. Options A and D are either too few or exceed the minimum.

The answer is True. With c color boxes and c+1 socks, by the pigeonhole principle at least one color box must contain 2 or more socks. The worst case is one sock of each color for the first c draws, and the (c+1)th draw must match one of the c colors already drawn, guaranteeing a pair.