Let $T_n$ denote a complete binary tree of depth $n$. Each internal node, $v$, of $T_n$ has two children denoted by $\lf(v)$ and $\rt(v)$. Consider the following game between two Players, Paul and Carole. For each internal node, $v$, Carole chooses $X(v) \in \{ \lf(v) , \rt(v) \}$. This naturally defines a path from the root, $\lambda$, of $T_n$ to one of its leaves as follows: $$\lambda, X(\lambda), X^2(\lambda ), \ldots, X^n(\lambda).$$ Paul has to find this path by asking questions of the following form:
\smallskip \centerline{$Q_v$:``Is $X(v) = \lf(v)$?''} \smallskip
\noindent The game proceeds in $r$ rounds. In every round Paul can
$k$ questions. Carole supplies the answers to these $k$ questions
in parallel.
We give necessary and sufficient conditions for Paul to win this game.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-35.ps.gz
DIMACS Home Page