Direkt zum Inhalt

Lexikon der Mathematik: Bachets Wägeproblem

lautet: Wieviele Gewichte braucht man mindestens, um mit einer Balkenwaage jedes ganzzahlige Gewicht von 1 bis 40 Pfund auswiegen zu können,

  1. wenn man die Gewichte nur auf eine Waagschale legen darf,
  2. wenn man beide Waagschalen benutzen darf?

Dieses Wägeproblem wurde schon im 13. Jahrhundert von Fibonacci erwähnt. Bachet beschrieb es in seinem 1612 erschienenen Buch „Problèmes plaisantes et delectables qui se font par les nombres“, weswegen es heute meist als Bachets Wägeproblem bezeichnet wird.

Im ersten Fall geht es darum, eine Menge G = {g1, …, gk}mit folgender Eigenschaft zu finden: Jede ganze Zahl N mit 1 ≤ NM = 40 läßt sich als Summe einer Auswahl von Gewichten aus G darstellen. Bachet gab die Lösung \begin{eqnarray}G=\{1,2,4,8,16,32\}.\end{eqnarray}

Daß dies eine Lösung ist, sieht man wie folgt: Jede natürliche Zahl N ≤ 40 besitzt eine (eindeutig bestimmte) Binärdarstellung \begin{eqnarray}N={({z}_{5}{z}_{4}{z}_{3}{z}_{2}{z}_{1}{z}_{0})}_{2}=\sum _{j=0}^{5}{z}_{j}\cdot {2}^{j}\end{eqnarray}mit 6 Ziffern z0, …, z5 ∈ {0, 1}. Um ein Gewicht von N Pfund auszuwiegen, bestimme man also zunächst die Binärdarstellung von N und wähle dann diejenigen Gewichte 2j, für die zj = 1 ist. Mit der Gewichtemenge G kann man auf diese Art jedes ganzzahlige Gewicht bis zum Maximum M = 63 Pfund auswiegen. Für M = 40 ist die Lösung (1) nicht eindeutig bestimmt; z. B. läßt sich mit der Gewichtemenge \begin{eqnarray}G^{\prime} =\{1,2,3,7,14,28\}\end{eqnarray}jedes ganzzahlige Gewicht bis 55 Pfund auswiegen. Man kann aber beweisen, daß für M = 40 mindestens 6 Gewichte notwendig sind.

Im zweiten Fall ist eine möglichst kleine Menge B = {b0, …, bk} derart gesucht, daß sich jede natürliche Zahl ≤ M = 40 in folgender Weise darstellen läßt: \begin{eqnarray}N={z}_{0}\cdot {b}_{0}+{z}_{1}\cdot {b}_{1}+{z}_{2}\cdot {b}_{2}+\ldots \end{eqnarray}mit „Ziffern“ z0, z1, … ∈ {−1, 0, 1}. Das ist so zu interpretieren: Man lege zunächst das auszuwiegende Gewicht N auf die linke Waagschale. Für jedes j = 0, 1, … lege man dann bj nach links, falls zj = −1, bj nach rechts, falls zj= 1, und man lasse bj weg, falls zj= 0. Bachet gab für diesen Fall die Lösung \begin{eqnarray}B=\{1,3,9,27\}.\end{eqnarray}

Abbildung 1 zum Lexikonartikel Bachets Wägeproblem
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Auswiegen von N = 25 Pfund mit Gewichten zu 16, 8 und 1 Pfund

Dies ist eine Lösung, denn jede ganze Zahl n mit \begin{eqnarray}|n|\le \frac{1}{2}({3}^{k}-1)\end{eqnarray}besitzt eine eindeutig bestimmte balancierte ternäre Darstellung mit k Ziffern z0, …, zk−1 ∈ {−1, 0, 1}. Für k = 4 ist \(\frac{1}{2}({3}^{k}-1)=40\), also benötigt man mindestens 4 Gewichte, und Bachets Lösung (3) ist die einzige Lösung dieses Wägeproblems.

Abbildung 2 zum Lexikonartikel Bachets Wägeproblem
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Auswiegen von N = 25 Pfund mit Gewichten zu 27, 3 und 1 Pfund

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos