Do Answers Help in Posing Questions
Sarmad Abbasi · 1998
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). Consider the following game between two Players, Paul and Carole. For each internal node, v, Carole chooses X(v) 2 fleft(v); right(v)g. This naturally defines a path from the root, , of T n to one of its leaves given by ; X();X 2 (); : : : ; X n (): 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. Key words: combinatorial games, two player perfect information games, adversary strategy This work is dedicated to Vicky Choi 1 Introduction Combinatorial games have been extensively studied[2]. The topic of this paper is the investigation of a game G(n; k; r) between two players. Let T n denote a complete binary tree with n ...