A simple solution to Ulam's liar game with one lie
From MaRDI portal
Publication:952012
DOI10.4171/EM/92zbMATH Open1230.91004arXiv0705.1220MaRDI QIDQ952012FDOQ952012
Deryk Osthus, Rachel Watkinson
Publication date: 5 November 2008
Published in: Elemente der Mathematik (Search for Journal in Brave)
Abstract: Ulam asked for the maximum number of questions required to determine an integer between one and one million by asking questions whose answer is `Yes' or `No' and where one untruthful answer is allowed. Pelc showed that the number of questions required is 25. Here we give a simple proof of this result.
Full work available at URL: https://arxiv.org/abs/0705.1220
Recommendations
Cites Work
- Solution of Ulam's problem on searching with a lie
- Coping with errors in binary search procedures
- Guess a Number-with Lying
- Title not available (Why is that?)
- Ulam's searching game with a fixed number of lies
- Title not available (Why is that?)
- Searching games with errors -- fifty years of coping with liars
- Fault-tolerant search algorithms. Reliable computation with unreliable information
- Title not available (Why is that?)
Cited In (9)
- Solution of Ulam's problem on searching with a lie
- Title not available (Why is that?)
- How to play the one-lie Rényi-Ulam game
- Ulam's searching game with a fixed number of lies
- The Interval Liar Game
- Guess a Number-with Lying
- \(Q\)-ary Rényi-Ulam pathological liar game with one lie
- Ulam's liar problem
- Ulam's pathological liar game with one half-lie
This page was built for publication: A simple solution to Ulam's liar game with one lie
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q952012)
