Ulam's liar problem

DOI10.1007/PL00009902MaRDI QIDQ1897482zbMATH OpenOpenAlexFDO

Authors Martin Aigner

Publication date 27 August 1995

Published in Mathematische Semesterberichte (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009902

Mathematics Subject Classification ID

2-person games (91A05)

Review text

Angenommen, jemand denkt sich eine Zahl \(x\) zwischen 1 und einer Million, und ein zweiter Spieler soll diese Zahl durch Fragen: ``Ist \(x\leq i\)? ermitteln. Da \(10^6< 2^{20}\) ist, kann die Zahl \(x\) durch die übliche Halbierungsmethode mit 20 Fragen bestimmt werden. Was aber, wenn der erste Spieler einmal (oder öfter) lügen darf? Wieviele Fragen werden dann benötigt? Dieses Spiel ist als ``Ulams Liar Problem bekannt geworden. Wir wollen das allgemeine Problem (\(n\) Zahlen, \(d\) Lügen) studieren und insbesondere Ulams Problem für ein Lüge lösen.

Recommendations

• Solution of Ulam's problem on binary search with two lies
• scientific article; zbMATH DE number 782050
• Optimal strategies against a liar
• A simple solution to Ulam's liar game with one lie
• Solution of Ulam's problem on searching with a lie

Cited in

(2)

• Solution of Ulam's problem on binary search with three lies
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Ulam's liar problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1897482)