@Article{Riv77a,
author = { Ronald L. Rivest },
title = { The game of {``$N$ questions''} on a tree },
journal = { Discrete Mathematics },
OPTyear = { 1977 },
OPTmonth = { February },
date = { 1977-02 },
volume = { 17 },
number = { 2 },
pages = { 181--186 },
doi = { 10.1016/0012-365X(77)90149-2 },
abstract = {
We consider the minimax number of questions required to
determine which leaf in a finite binary tree $T$ your
opponent has chosen, where each question may ask if the leaf
is in a specified subtree of $T$. The requisite number of
questions is shown to be approximately the lagorithm (base~$\phi$)
of the number of leaves in $T$ as $T$ becomes large, where
$\phi=1.61803\ldots$ is the ``golden ratio''. Specifically,
$q$ questions are sufficient to reduce the number of possibilities
by a factor of $2/F_{q+3}$ (where $F_i$ is the $i$th Fibonacci
number), and this is the best possible.
},
}