DIMACS TR: 98-35

Do Answers Help in Posing Questions?

Author: Sarmad Abbasi


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