7.6 Worst-case reasoning

A question asking what is guaranteed is different from one asking what is likely. You must allow the most inconvenient sequence of choices that the rules permit. If a successful outcome is unavoidable even then, you have a worst-case guarantee. This appears in drawing objects without looking, dividing items among categories, and deciding how many questions an algorithm needs.

This is intermediate counting and reasoning. MIT's counting notes introduce the pigeonhole principle; the broader MIT course has more exercises. The casework method from Module 7.5 helps when the categories have different capacities.

A basic idea: delay success as long as possible

Imagine a drawer with socks in three colours and enough socks of each colour. How many must you draw without looking to guarantee a same-colour pair? The first three could all have different colours; no pair is forced. A fourth sock must match one of those three colours. Thus the guarantee is four draws. The first three form a counterexample to any smaller claimed guarantee, while the fourth proves the upper bound.

A quick tour of guarantees

The pigeonhole principle says that placing more than $m$ objects into $m$ categories forces some category to hold at least two. More generally, among $N$ objects in $m$ categories, one category has at least $\lceil N/m\rceil$ objects. For a guaranteed threshold, find the largest unsuccessful arrangement and add one; then check that such an unsuccessful arrangement really can occur.

Worst-case reasoning also applies to algorithms. A yes-or-no question can distinguish at most two possibilities. After $q$ such answers, there are at most $2^q$ answer patterns. To identify one of $N$ equally possible labels in every case, we need $2^q\ge N$. This is a lower bound; an actual strategy must still show that the bound can be reached.

Do not replace a guarantee with an average. Randomly drawn socks will often match earlier, but “often” does not prove the fourth-draw threshold.

Application 1: a matching sock

The drawer contains at least four socks of each of three colours. What is the smallest draw count that guarantees two of the same colour?

1. Draw one of each colour: three socks with no match are possible, so three draws do not guarantee success.
2. The fourth sock must have one of the same three colours, making a pair.
3. Therefore the smallest guaranteed number is $4$.

Application 2: identify a hidden number

A hidden integer is one of $1,2,\ldots,16$. You may ask yes-or-no questions whose answers can guide later questions. How many questions are needed in the worst case?

1. Three questions produce at most $2^3=8$ different answer strings, too few to distinguish $16$ integers. At least four are necessary.
2. Ask whether the number is greater than $8$. That leaves a group of eight; ask whether it is in the upper half of that group, then repeat twice more.
3. The candidate group shrinks $16\to8\to4\to2\to1$. Four questions are sufficient, so the worst-case minimum is four.