Vor dir stehen zehn Säcke mit Goldmünzen, durchnummeriert von 1 bis 10. Jeder Sack enthält reichlich Münzen. Eine echte Münze wiegt genau 10 Gramm, doch in einem Sack sind sämtliche Münzen Fälschungen und wiegen nur 9 Gramm.
Dir steht eine digitale Waage zur Verfügung, die das exakte Gewicht anzeigt – aber du darfst sie nur ein einziges Mal benutzen.
Wie findest du den Sack mit den Fälschungen?
Hinweis anzeigen
Du darfst beliebig viele Münzen aus beliebig vielen Säcken gleichzeitig wiegen. Gib jedem Sack eine andere „Stimme" im Gesamtgewicht.
Lösung
Die Lösung ist ausgeblendet. Nimm dir erst selbst Zeit für die Aufgabe – der Aha-Moment lässt sich nicht nachholen.
Wirklich aufdecken?
Hast du es ernsthaft versucht – und den Hinweis gelesen? Danach gibt es kein Zurück im Kopf.
Lösung
Das Verfahren. Nimm aus Sack $i$ genau $i$ Münzen, also 1 Münze aus Sack 1, 2 aus Sack 2, …, 10 aus Sack 10. Das sind zusammen
Die Auswertung. Wären alle echt, zeigte die Waage $55 \cdot 10 = 550$ Gramm. Ist Sack $k$ der gefälschte, so sind genau $k$ der gewogenen Münzen je 1 Gramm zu leicht. Das angezeigte Gewicht ist dann
$$
G = 550 - k \qquad \text{Gramm}.
$$
Die Fehlmenge in Gramm nennt also direkt die Nummer des Sacks:
$$
k = 550 - G .
$$
Zeigt die Waage etwa 543 Gramm, so ist $k = 7$: Sack 7 enthält die Fälschungen. $\blacksquare$
Warum das funktioniert
Entscheidend ist, dass die zehn möglichen Fehlmengen $1, 2, \dots, 10$ paarweise verschieden sind – jeder Sack hinterlässt eine eigene Signatur im Gesamtgewicht. Eine einzige Zahl trägt so die ganze Information.
Zwei Verschärfungen
Wäre unbekannt, ob die falschen Münzen leichter oder schwerer sind, geht das Verfahren unverändert durch: Dann ist $|550 - G| = k$, und das Vorzeichen von $550 - G$ verrät zusätzlich die Richtung.
Dürften sogar mehrere Säcke gefälscht sein, nimmt man aus Sack $i$ nicht $i$, sondern $2^{i-1}$ Münzen. Die Fehlmenge in Gramm ist dann die Summe der $2^{i-1}$ über alle gefälschten Säcke – ihre Binärdarstellung nennt jeden einzelnen. Für zehn Säcke braucht man dafür allerdings $1 + 2 + \dots + 512 = 1023$ Münzen.