Abstract   The Ulam-Renyi game is a classical model for the problem of determining the minimum number of queries to find an unknown number in a finite set when up to a finite number  e  of the answers may be lies. In the variant, we introduce in this paper, questions with  q  many possible answers are allowed and lies are constrained by a prescribed graph. We essentially solve the problem exact asymptotically under some symmetry-hypothesis. All our strategies are implementable by procedures which use adaptiveness only once.
['Ferdinando Cicalese', 'Christian Deppe']
Q -ary Ulam-Rényi game with constrained lies