How Many Socks Guarantee a Pair? Worst-Case Thinking

If a drawer holds socks in k colors, you need to pull out k + 1 socks to be certain of a matching pair. The reasoning is to imagine the worst luck: you draw one sock of every color without a match, and then the very next sock has to match one of them. This "plan for the worst case" idea is often called the pigeonhole principle, and it solves a whole family of drawer puzzles.

NRICH, the mathematics project at the University of Cambridge, has a task built on it called Counting Socks (taken from the UKMT Mathematical Challenges). A box holds two white, three blue and four grey socks, and three of them have holes in unknown colors. The task asks how many socks must be taken to be certain of a same-color pair without holes. Worst-case thinking gives 7: the three holey socks, one good sock of each of the three colors, and then one more. The puzzles below use different numbers, and each answer was confirmed by checking every possible draw.

1. The method in three steps

1. List what could go wrong. The worst case is the draw that gets as close as possible to your goal without reaching it.
2. Count the socks in that worst draw. For "one of each color but no pair", that is the number of colors.
3. Add one. Any sock after the worst draw completes the goal.

The guarantee must hold for every possible draw, not just the likely ones. That is why the answer depends on the colors and not on how many socks of each color the drawer holds, as long as each color has enough socks to supply the worst case.

2. Puzzle 1: any matching pair

A drawer holds 5 red, 4 blue and 3 green socks. You pick in the dark. How many must you take to be certain of two socks of the same color?

Answer: 4. Worst case is one red, one blue, one green. The fourth sock matches one of them. Three socks might not be enough, so 4 is the smallest guarantee.

3. Puzzle 2: three of a kind

Same drawer. How many socks guarantee three of the same color?

Answer: 7. The worst case is two of each color with no third: 2 + 2 + 2 = 6 socks. The 7th sock gives three of one color. Every color has at least 3 socks, so the worst case can really happen.

4. Puzzle 3: a pair of a chosen color

Same drawer again. You specifically need two red socks. How many must you take to be certain?

Answer: 9. Now bad luck can take every non-red sock first: 4 blue and 3 green is 7 socks. Then you need 2 more to get two reds, so 7 + 2 = 9. Compare this with puzzle 1. Asking for a specific color is far costlier than asking for any match. For two green socks the answer is 11, because there are 9 non-green socks.

5. Puzzle 4: left and right gloves

A box holds 6 left gloves and 6 right gloves, all in one color. How many must you take to be certain of having one left and one right?

Answer: 7. Worst case is that all 6 gloves you pull out are lefts (or all rights), and the 7th must be the other hand. A full check of every possible draw confirms 7, not 6.

6. Puzzle 5: some socks have holes

A drawer has 3 red, 4 green and 2 black socks. Two socks have holes, and you do not know which ones. How many must you take to be certain of a matching pair with no holes?

Answer: 6. The worst case is that you draw both holey socks plus one good sock of each color, which is 2 + 3 = 5 socks and no good pair. The 6th sock then completes a good pair. Checking all draws and all possible hole placements confirms that 5 can fail and 6 cannot. For reference, with no holey socks the answer is 4, with one holey sock 5, and with three holey socks 7. Each extra holey sock adds one to the answer.

7. When the pigeonhole idea breaks down

The method needs the colors to run out. If a color has only one sock, you can never get a pair in it, and that color should be removed from the count of "usable" colors. In puzzle 5, if all the black socks were the holey ones, there would be fewer usable colors, which could only speed things up. The worst case, where every color is still available, is the one that sets the answer.

A related NRICH task, Mixed-Up Socks, goes the other way: start with three pairs of socks and mix them so that no mismatched pair is the same as another. That asks you to build arrangements, not guarantees, but both reward the habit of testing every case.

8. Key takeaways

• To be certain of a matching pair among k colors, take k + 1 socks.
• To be certain of m of the same color, take k(m - 1) + 1 socks, as long as every color has at least m socks.
• To be certain of a specific color, assume every other sock comes out first.
• Holey, odd or mismatched socks each add one to the worst case.
• A guarantee means "for every possible draw", so test the unluckiest one.