Solution of Ulam's problem on binary search with two lies

DOI10.1016/0097-3165(88)90065-9MaRDI QIDQ1114408zbMATH OpenOpenAlexFDO

Authors Jurek Czyzowicz, Andrzej Pelc, Daniele Mundici

Publication date 1988

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(88)90065-9

zbMATH Keywords

binary search with two lies

Mathematics Subject Classification ID

Searching and sorting (68P10) 2-person games (91A05)

Review text

Someone thinks of a number between one and one million (which is just less than \(2^{20})\). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first: Is the number in the first half million ? then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in less than \(\log_ 2(1,000,000)\). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer ? [\textit{S. M. Ulam}, ``Adventures of a mathematician (Scribner's (New York, 1976; Zbl 0352.01009), p. 281)]. We prove that Ulam's problem has the following solution: Theorem. Twenty-nine is the least number of yes-no questions sufficient to find an integer between one and one million, if up to two lies are allowed.

Recommendations

• Solution of Ulam's problem on searching with a lie
• scientific article; zbMATH DE number 782050
• Strategies for the Renyi--Ulam game with fixed number of lies
• Ulam's searching game with two lies
• Searching with lies: The Ulam problem

Cited in

(19)

• Solution of Ulam's problem on searching with a lie
• Ulam's searching game with lies
• Solution of Ulam's problem on binary search with three lies
• Searching with lies: The Ulam problem
• Group testing with unreliable tests
• A nonadaptive version of Ulam's problem with one lie
• Ulam's searching game with three lies
• Ulam's liar problem
• Optimal strategies against a liar
• \(Q\)-ary search with one Lie and bi-interval queries
• Variable continuation in solving a problem in discrete mathematics
• Guess a Number-with Lying
• Coding Theory Applied to a Problem of Ulam
• scientific article; zbMATH DE number 782050 (Why is no real title available?)
• An improved upper-bound for Rivest et al.'s half-lie problem
• Searching games with errors -- fifty years of coping with liars
• Rényi-Berlekamp-Ulam searching game with bi-interval queries and two lies
• Ulam's searching game with two lies
• Searching with a forbidden lie pattern in responses

This page was built for publication: Solution of Ulam's problem on binary search with two lies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114408)