Gefälschte Münzen
Aus den zahlreichen Wägeproblemen sei an dieser Stelle ein Klassiker mit einer verblüffend einfachen Lösung angeführt:
Man hat 10 Haufen von Münzen und jeder Haufen enthält 10 Centstücke.
Ein gesamter Haufen ist gefälscht, aber man weiß auch, dass jede gefälschte Münze ein Gramm mehr als eine echte wiegt.
Man darf die Münzen auf einer Neigungswaage wägen.
Welche minimale Anzahl von Wägungen ist nötig, um den gefälschten Haufen eindeutig zu ermitteln ?
Der gefälschte Haufen lässt sich durch eine einzige Wägung von Münzen ermitteln.
Man entfernt eine Münze aus dem ersten Haufen, zwei Münzen aus dem zweiten, drei aus dem dritten und so weiter, bis man schließlich alle zehn Münzen aus dem zehnten Haufen entfernt.
Damit entsteht aus der ursprünglichen Anordnung
10
10
10
10
10
10
10
10
10
10
die neue Anordnung
9
8
7
6
5
4
3
2
1
0
Nun wird auf einer Waage die Menge der entfernten Münzen gewogen. Das "Übergewicht" dieser Menge von Münzen, in Gramm gemessen, entspricht der Zahl des gefälschten Haufens.
Besteht nämlich beispielsweise der dritte Haufen aus lauter gefälschten Münzen, so besitzt dieser ein Gewicht von 3 ⋅ (x + 1) = 3x + 3 Gramm.
Die ursprüngliche Anordnung
10
10
10
10
10
10
10
10
10
10
besitzt ein Gewicht von
10x + 10x + 10 ⋅ (x + 1) + 10x + 10x + 10x + 10x + 10x + 10x + 10x = 100x + 10 Gramm,
während die neue Anordnung
9
8
7
6
5
4
3
2
1
0
das Gesamtgewicht
9x + 8x + 7 ⋅ (x + 1) + 6x + 5x + 4x + 3x + 2x + 1x + 0 = 45x + 7 Gramm
aufweist.
Damit besitzt die Menge der entfernten Münzen
1
2
3
4
5
6
7
8
9
10
das Gesamtgewicht
1x + 2x + 3 ⋅ (x + 1) + 4x + 5x + 6x + 7x + 8x + 9x + 10x = 55x + 3 Gramm.
Das "Übergewicht" dieser Menge von 3 Gramm weist daher auf den dritten Haufen als gefälschten Haufen hin.