Ulam's liar problem (Q1897482)

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.