14.1 Counting arguments

Most puzzles in this chapter look as if they need ingenuity, yet nearly all of them yield to a few counting arguments applied with care. The first is the worst case. When a question asks how many objects must be drawn to guarantee some outcome, we imagine an adversary who supplies the objects in the least helpful order, and we count how long he can delay the outcome. One more object then forces it. In its simplest form this is the pigeonhole principle: if more than \(k\) objects are placed in \(k\) boxes, some box holds at least two. More generally, if \(N\) objects are placed in \(k\) boxes, some box holds at least \(\lceil N/k\rceil\). A bag containing \(r\) red, \(b\) blue and \(g\) green balls, with \(g\ge b\ge r\), must be emptied of \(g + b + 1\) balls before a ball of every colour is certain, because the adversary first hands over all the green and all the blue balls.

The second argument is conservation of a total. If the digits \(1, 2, \dots, 9\) are each written once in a set of cells, their sum is always

\[1 + 2 + \cdots + 9 = \frac{9\times 10}{2} = \boxed{45},\]

so when the sums of some groups of cells are given, the content of the remaining cells follows by subtraction. Statements of the type “all but two are cows” yield to the same idea: if there are \(N\) animals and \(c\) of them are cows, then \(N - c = 2\). Writing one such equation for each kind and adding them gives an equation for \(N\) alone.

The third argument concerns a quantity that changes by a fixed amount at every step. A straight cut through a single piece of chocolate turns one piece into two, so each cut raises the number of pieces by exactly one, and a bar that must end as \(n\) separate pieces needs exactly \(n - 1\) cuts whatever the order. Similarly, every match in a tournament distributes a definite number of points: with 3 points for a win and 1 for a draw, a decisive match gives 3 points in total and a drawn one gives 2. If \(T\) teams each play \(m\) matches, the number of matches is \(Tm/2\), because each match involves two teams, and the total number of points lies between \(2\times Tm/2\) (all draws) and \(3\times Tm/2\) (no draws).

The last counting idea is that of information. A question with a Yes/No answer can at best halve the set of possibilities that remain, so \(n\) such questions can distinguish at most \(2^n\) cases. To identify one of \(N\) equally possible cases we therefore need the least \(n\) with

\[\boxed{2^n \ge N},\]

and this many questions always suffice, by repeatedly asking whether the answer lies in the first half of what is left.