COCOA Talk: 99-01

Speaker: 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 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