Renyi-Berlekamp-Ulam searching game with bi-interval queries and two lies

摘要

We consider the following searching game: there are two players, say Questioner and Responder. Responder chooses a number x is an element of S-n = (1, 2, ..., n}, Questioner has to find out the number x by asking hi-interval queries and Responder is allowed to lie at most two times throughout the game. The minimal number q*(n) of bi-interval queries sufficient to find the unknown integer x is determined for all integers n. This solves completely Renyi-Berlekamp-Ulam searching game with bi-interval queries and two lies, partially solved by Mundici and Trombetta. Their solution applied only to the case when n is a power of 2. (C) 2015 Elsevier B.V. All rights reserved.