We study a new variant of the classical 20 question game with lies (a.k.a. Ulam-Rényi game). The Ulam-Rényi game models the problem of identifying an initially unknown m-bit number by asking subset questions, where up to e of the answers might be mendacious. In the variant considered in this paper, we set an additional constraint on the type of questions, namely, that the subsets they ask for should be the union of at most k intervals for some k > 0 fixed beforehand. We show that for any e and m, there exists k only depending on e such that strategies using k-interval question are as powerful (in terms of the minimum number of queries needed) as the best strategies using arbitrary membership questions.
Perfect Strategies for the Ulam-Rényi Game with Multi-interval Questions
Cicalese, Ferdinando
2014-01-01
Abstract
We study a new variant of the classical 20 question game with lies (a.k.a. Ulam-Rényi game). The Ulam-Rényi game models the problem of identifying an initially unknown m-bit number by asking subset questions, where up to e of the answers might be mendacious. In the variant considered in this paper, we set an additional constraint on the type of questions, namely, that the subsets they ask for should be the union of at most k intervals for some k > 0 fixed beforehand. We show that for any e and m, there exists k only depending on e such that strategies using k-interval question are as powerful (in terms of the minimum number of queries needed) as the best strategies using arbitrary membership questions.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
