Socks in the Dark

  • Easy
  • Arrangement puzzles
  • Tests: Reasoning about the worst case, not the likely one

The puzzle

A drawer holds a large number of black socks and blue socks, mixed together. The room is dark and you cannot tell them apart by touch.

How many socks must you take out to be certain of having a matching pair?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

You are not asked for the likely number. You are asked for the number that cannot fail.

Hint 2

What is the worst that can happen with two socks?

Show the answer Hide the answer

Three.

How to get there

Two socks can be one of each colour, which is no pair - so two is not enough.

With three socks and only two colours, two of them must share a colour. There is nowhere else for the third to go.

So three always works and two sometimes fails, which makes three the answer. Note it does not depend on how many socks are in the drawer.

The technique worth keeping

The pigeonhole principle: n+1 items in n categories force a repeat. Ask for the worst case rather than the typical one, and the answer stops depending on the quantities you were not given.