Solution of Ulam's problem on binary search with two lies
type: Item
instance of: scholarly article
title: Solution of Ulam's problem on binary search with two lies
zbMATH Open document ID: 0662.68059
DOI: 10.1016/0097-3165(88)90065-9
author: Jurek Czyzowicz
author: Andrzej Pelc
author: Daniele Mundici
published in: Journal of Combinatorial Theory. Series A
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 91A05
zbMATH DE Number: 4082990
zbMATH Keywords: binary search with two lies
MaRDI profile type: Publication
full work available at URL: 0097-3165(88)90065-9
OpenAlex ID: W2031876674
description: scientific article; zbMATH DE number 4082990