## DIMACS TR: 98-35

## Do Answers Help in Posing Questions?

### Author: Sarmad Abbasi

**
ABSTRACT
**

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