Solution of Ulam's problem on searching with a lie (Q1090471): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0097-3165(87)90065-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2058515835 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5568914 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coping with known patterns of lies in a search game / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coping with errors in binary search procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Guess a Number-with Lying / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4121861 / rank | |||
Normal rank |
Latest revision as of 19:15, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solution of Ulam's problem on searching with a lie |
scientific article |
Statements
Solution of Ulam's problem on searching with a lie (English)
0 references
1987
0 references
\textit{S. M. Ulam} [''Adventures of a mathematician'' (1976; Zbl 0352.01009)] stated the following problem: what is the minimal number of yes-no queries needed to find an integer between one and one million, if one lie is allowed among the answers. \textit{R. L. Rivest}, \textit{A. R. Meyer}, \textit{D. J. Kleitman}, \textit{K. Winkelmann} and \textit{J. Spencer} [J. Comput. Syst. Sci. 20, 396-404 (1980; Zbl 0443.68043)] and \textit{J. Spencer} [Math. Mag. 57, 105-108 (1984; Zbl 0538.90110)] gave partial solutions by establishing bounds for the minimal number of queries necessary to find a number in the set \(\{\) 1,...,n\(\}\). Applied to the original question both solutions yield two possibilities: 25 or 26. We give an exact solution of Ulam's problem in the general case. For \(n=10^ 6\) the answer turns out to be 25. We also give an algorithm to perform the search using the minimal number of queries.
0 references
searching
0 references
minimal number of yes-no queries
0 references