A simple solution to Ulam's liar game with one lie

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

zbMATH Keywords

Ulam's liar game

Mathematics Subject Classification ID

2-person games (91A05) Other game-theoretic models (91A40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Solution of Ulam's problem on searching with a lie
• Coping with errors in binary search procedures
• Guess a Number-with Lying
• Ulam's searching game with a fixed number of lies
• Searching games with errors -- fifty years of coping with liars
• Fault-tolerant search algorithms. Reliable computation with unreliable information

Cited In (5)

• 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
• \(Q\)-ary Rényi-Ulam pathological liar game with one lie
• Ulam's liar problem

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)