## COCOA Talk: 99-01

## Do Answers Help in Posing Questions?

### Speaker: 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 left(v) and right(v).
We Consider the following game between two Players, Paul and Carole.
For each internal node, v, Carole chooses X(v) in { left(v) \right(v}.
This naturally defines a path from the root, r, of T_n to one
of its leaves given by
r , X(r), X^2(r), ... , X^n(r).
Paul has to find this path by asking questions of the form:
Q_v: ``Is $X(v) = \left(v)$?''
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.

DIMACS Home Page