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

2007/05/09 by Deryk Osthus, Osthus, Deryk, Rachel Watkinson +1
Mathematics · #94B99 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:94B99

paper · pdf · doi:10.48550/arxiv.0705.1220

arxiv created 2007/05/09 · arxiv updated 2009/12/01

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.

Related

• Twenty Questions Games Always End With Yes
• Algorithm to Prove Formulas for the Expected Number of Questions in Mastermind Games
• The entropy of lies: playing twenty questions with a liar
• Discussion of Twenty Questions Problem
• On the Multi-Interval Ulam-Rényi Game: for 3 lies 4 intervals suffice