Gegeben sind N außerlich gleiche Säckchen, die Sand enthalten (die Anzahl N beträgt dabei mindestens 2). Eines der Säckchen enthält goldhaltigen Sand und ist daher etwas schwerer als die anderen. Alle anderen Säckchen sind gleich schwer. Sie erhalten eine Balkenwaage, mit der Sie das Gewicht von jeweils zwei Säckchen vergleichen können, um festzustellen, welches der beiden Säckchen schwerer ist bzw. ob beide Säckchen gleich schwer sind.
Ihr Aufgabe besteht nun darin, einen Algorithmus anzugeben, mit dem sich systematisch das Säckchen mit dem Goldanteil ermitteln lässt.
Tool: In der folgenden interaktiven Simulation können Sie verschiedene Lösungsstrategien selbst durchspielen, um ein Lösungsverfahren zu entwickeln und zu testen. Ziehen Sie die Säckchen auf die freien Felder in der Waage, um ihr Gewicht zu vergleichen. Die Fläche in der Mitte können Sie nutzen, um die Säckchen während des Lösungsverfahrens zu verwalten (z. B. oben die noch nicht betrachteten Säckchen, unten die bereits betrachteten Säckchen). Das gesuchte Säckchen können Sie im grünen Feld rechts platzieren.
Klicken Sie auf “Lösung anzeigen”, wenn Sie glauben, das richtige Säckchen gefunden zu haben. Mit den anderen Schaltflächen lässt sich die Simulation neu starten und die Anzahl der Säckchen ändern.