Eine Ja-Nein-Frage teilt die verbliebenen Möglichkeiten idealerweise in zwei gleich große Gruppen. Nach der ersten Antwort bleiben von einer Million Kandidaten ungefähr 500.000, nach der zweiten 250.000. Bei jeder weiteren Frage halbiert sich die Menge erneut. Zwanzig solcher Entscheidungen besitzen insgesamt 2 hoch 20, also 1.048.576, mögliche Antwortfolgen. Damit lässt sich unter günstigen Bedingungen eine Zahl aus einem Bereich von über einer Million Möglichkeiten eindeutig identifizieren.
Die Idee steckt hinter der binären Suche in sortierten Daten und ist mit der Speicherung von Informationen in Bits verwandt. Wichtig ist, dass die Fragen tatsächlich so gewählt werden können, dass sie die Kandidaten sinnvoll trennen. Wahllos gestellte Fragen besitzen nicht automatisch dieselbe Effizienz.
Gilt bei eindeutigen wahrheitsgemäßen Antworten, zulässigen optimalen Fragen und höchstens 1.048.576 unterscheidbaren Zuständen. Das Spiel ist eine exakte Halbierung eines endlichen Suchbereichs, keine Gedankenlesetechnik.
Datenstand: Mathematische Schlussprüfung: 20.10.2026
So wurde gerechnet
2^20 = 1.048.576; 2^19 = 524.288. Für N = 1.000.000 mögliche ganze Zahlen reichen ceil(log2(N)) = 20 Ja-Nein-Antworten im schlechtesten Fall. Bei der Frage „Ist die Zahl höchstens m?“ verbleibt entweder [unten,m] oder [m+1,oben].
Das ergänzende Experiment oder Schaubild ist mit JavaScript verfügbar.
