Hemmes mathematische Rätsel: Mit welchen Gewichtssteinen kann man möglichst gut wiegen?
Der französische Mathematiker Claude Gaspar Bachet des Méziriac (1581–1638) wurde bekannt durch seine Übersetzung der »Arithmetica« von Diophant von Alexandria aus dem Griechischen ins Lateinische. Aber er schrieb auch ein Buch über die Unterhaltungsmathematik mit dem Titel »Problèmes plaisants et délectables qui sont font par des nombres«, das 1612 erschien. Darin fragt er:
In welche Stücke muss man einen 40-pfündigen Gewichtsstein zerbrechen, damit man damit auf einer Balkenwaage jedes ganzzahlige Gewicht von 1 bis zu 40 Pfund abwiegen kann?
Ich habe Bachets Frage jedoch ein wenig verändert:
Mit n Gewichtssteinen soll man jedes ganzzahlige Gewicht von 1 bis N Pfund wiegen können. Dazu dürfen die Steine in nur eine der beiden Schalen einer Balkenwaage gelegt werden. In die andere füllt man das Wägegut.
Welche Gewichte müssen die n Steine haben, damit N möglichst groß wird?
Für jeden einzelnen der n Gewichtssteine gibt es zwei Möglichkeiten: Entweder liegt er in der Waagschale oder nicht. Für alle n Steine zusammen sind dies 2n Möglichkeiten. Mit n Steinen lassen sich also höchstens alle Gewichte von 0 bis 2n − 1 Pfund abwiegen.
Diese Obergrenze kann man tatsächlich erreichen, wenn die Steine Gewichte von 20 = 1, 21 = 2, 22 = 4, 23 = 8, … und 2n − 1 Pfund haben. Das ist auch leicht zu sehen, wenn man sich die ersten paar Gewichte ansieht.
1 = 1
2 = 2
3 = 2 + 1
4 = 4
5 = 4 + 1
6 = 4 + 2
7 = 4 + 2 + 1
8 = 8
9 = 8 + 1
10 = 8 + 2
11 = 8 + 2 + 1
12 = 8 + 4
13 = 8 + 4 + 1
14 = 8 + 4 + 2
15 = 8 + 4 + 2 + 1
Schreiben Sie uns!
1 Beitrag anzeigen