×

zbMATH — the first resource for mathematics

Rényi-Berlekamp-Ulam searching game with bi-interval queries and two lies. (English) Zbl 1338.91041
Summary: We consider the following searching game: there are two players, say Questioner and Responder. Responder chooses a number \(x\in S_n=\{1,2, \ldots,n\}\), Questioner has to find out the number \(x\) by asking bi-interval queries and Responder is allowed to lie at most two times throughout the game. The minimal number \(q^\ast(n)\) of bi-interval queries sufficient to find the unknown integer \(x\) is determined for all integers \(n\). This solves completely Rényi-Berlekamp-Ulam searching game with bi-interval queries and two lies, partially solved by D. Mundici and A. Trombetta [Theor. Comput. Sci. 182, No. 1–2, 217–232 (1997; Zbl 0902.90191)]. Their solution applied only to the case when \(n\) is a power of 2.
MSC:
91A46 Combinatorial games
68P10 Searching and sorting
91A05 2-person games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aigner, M., Searching with lies, J. Combin. Theory Ser. A, 74, 43-56, (1996) · Zbl 0846.90149
[2] Berlekamp, E. R., Block coding for the binary symmetric channel with feedback, (Mann, H. B., Error-correcting Codes, (1968), Wiley New York), 330-335
[3] Cicalese, F., Fault-tolerant search algorithms, (2013), Springer-Verlag · Zbl 1295.68006
[4] Cicalese, F., Perfect strategies for the Ulam-Rényi game with multi-interval questions, Theory Comput. Syst., 54, 4, 578-594, (2014) · Zbl 1303.68044
[5] Cicalese, F.; Mundici, D.; Vaccaro, U., Rota-metropolis cubic logic and Ulam-Rényi games, (Crapo, H.; Senato, D., Algebraic Combinatorics and Computer Science: A Tribute to Gian-Carlo Rota, (2001), Spinger-Verlag), 197-244 · Zbl 0978.03045
[6] Cicalese, F.; Vaccaro, U., Optimal strategies against a liar, Theoret. Comput. Sci., 230, 167-193, (2000) · Zbl 0966.91014
[7] Czyzowicz, J.; Mundici, D.; Pelc, A., Solution of ulam’s problem on binary search with two lies, J. Combin. Theory Ser. A, 49, 384-388, (1998) · Zbl 0662.68059
[8] Czyzowicz, J.; Mundici, D.; Pelc, A., Ulam’s searching game with lies, J. Combin. Theory Ser. A, 52, 62-76, (1989) · Zbl 0674.90110
[9] Deppe, C., Solution of ulam’s searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes, Discrete Math., 224, 79-98, (2000) · Zbl 0967.91008
[10] Deppe, C., Coding with feedback and searching with lies, (Entropy, Search, Complexity, (2007), Springer-Verlag), 27-70
[11] Ellis, R. B.; Ponomarenko, Vadim; Yan, C. H., The renyi-Ulam pathological liar game with a fixed number of lies, J. Combin. Theory Ser. A, 112, 2, 328-336, (2005) · Zbl 1121.91023
[12] Guzicki, W., Ulam’s searching game with two lies, J. Combin. Theory Ser. A, 54, 1-19, (1990) · Zbl 0712.68027
[13] Hill, R., Searching with lies, (Rowlinson, P., Surveys in Combinatorics, Lecture Note Series, vol. 218, (1995), Cambridge Univ. Press Cambridge), 41-70 · Zbl 0833.90129
[14] Liu, W. A.; Zhang, Q. M.; Nie, Z. K., Searching for a counterfeit coin with two unreliable weighings, Discrete Appl. Math., 150, 160-181, (2005) · Zbl 1071.05003
[15] Malinowski, A., K-ary searching with a Lie, Ars Combin., 37, 301-308, (1994) · Zbl 0820.68039
[16] Mundici, D.; Trombetta, A., Optimal comparison strategies in ulam’s searching game with two errors, Theoret. Comput. Sci., 182, 217-232, (1997) · Zbl 0902.90191
[17] Negro, A.; Sereno, M., Ulam’s searching game with three lies, Adv. Appl. Math., 13, 404-428, (1992) · Zbl 0773.68022
[18] Negro, A.; Sereno, M., Solution of ulam’s problem on binary search with three lies, J. Combin. Theory Ser. A, 59, 149-154, (1992) · Zbl 0763.05004
[19] Pelc, A., Solution of ulam’s problem on searching with a Lie, J. Combin. Theory Ser. A, 44, 129-140, (1987) · Zbl 0621.68056
[20] Pelc, A., Searching games with errors-fifty years of coping with liars, Theoret. Comput. Sci., 270, 71-109, (2002) · Zbl 0984.68041
[21] Pelc, A., Detecting a counterfeit coin with unreliable weighings, Ars Combin., 27, 181-192, (1989) · Zbl 0719.05008
[22] Rényi, A., On a problem of information theory, MTA Mat. Kut. Int. Kozl., 6B, 505-516, (1961) · Zbl 0126.35605
[23] Spencer, J., Ulam’s searching game with a fixed number of lies, Theoret. Comput. Sci., 95, 2, 307-321, (1992) · Zbl 0749.90102
[24] Ulam, S. M., Adventures of a Mathematician, (1976), Scribner’s New York · Zbl 0352.01009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.