= Solution
The procedure in part (i) sometimes needs five tests, for items one or two. A binary <decision tree> of height $N$ has at most $2^N$ leaves, so distinguishing ten possibilities requires $N\geq\lceil\log_2 10\rceil=4$.
A <prefix code> attaining this worst-case bound is
$$
\begin{array}{c|cccccccccc}
\text{item}&1&2&3&4&5&6&7&8&9&10\\\hline
\text{code}&1100&1101&1110&1111&000&001&010&011&100&101.
\end{array}
$$
Use the same subset-testing rule. \b[The minimum worst-case number is four, so the expected-optimal procedure is not worst-case optimal.] This four-test procedure has expectation $175/55$, illustrating the small cost of imposing the smaller maximum depth.
Back to article page
