Vor dir liegen neun äusserlich gleiche Münzen. Acht davon wiegen exakt gleich viel, eine ist schwerer. Zur Verfügung steht eine Balkenwaage, die nur anzeigt, welche Seite schwerer ist oder ob Gleichstand herrscht.
Finde die schwere Münze mit zwei Wägungen – und begründe, dass eine einzige Wägung niemals reichen kann.
Eine Wägung hat drei mögliche Ausgänge, nicht zwei. Wie viele Münzen lassen sich damit höchstens unterscheiden?
Die Lösung ist ausgeblendet. Nimm dir erst selbst Zeit für die Aufgabe – der Aha-Moment lässt sich nicht nachholen.
Hast du es ernsthaft versucht – und den Hinweis gelesen? Danach gibt es kein Zurück im Kopf.
Lösung
Das Verfahren. Teile die Münzen in drei Gruppen zu je drei Stück: $A = \{1,2,3\}$, $B = \{4,5,6\}$, $C = \{7,8,9\}$.
Erste Wägung: $A$ gegen $B$.
In jedem Fall bleibt eine Dreiergruppe übrig, die die schwere Münze enthält.
Zweite Wägung: Aus dieser Gruppe legst du eine beliebige Münze links, eine zweite rechts, die dritte beiseite.
Nach zwei Wägungen steht die Münze also in jedem Fall fest.
Eine Wägung reicht nicht. Eine Wägung hat genau drei mögliche Ausgänge (links schwerer, rechts schwerer, Gleichstand). Ein Verfahren mit einer Wägung kann deshalb höchstens drei verschiedene Antworten liefern, es gibt aber neun mögliche Lösungen. Nach dem Schubfachprinzip müssten mindestens zwei verschiedene Münzen zum selben Ausgang führen – in diesem Fall liesse sich nicht entscheiden, welche der beiden die schwere ist. $\blacksquare$
Dasselbe Argument liefert die Grenze für $k$ Wägungen: Es gibt $3^k$ mögliche Ergebnisfolgen, also lassen sich höchstens $3^k$ Münzen behandeln. Für $k = 2$ sind das genau $9$ – das Verfahren oben ist somit optimal, und für 27 Münzen genügen auf dieselbe Weise drei Wägungen.