Ein Rätsel zur elementaren Informationstheorie

Dieser Text ist noch in Bearbeitung.

Einleitung

Gegeben seien acht gleichaussehende Goldmünzen. Eine von ihnen sei gefälscht und nur vergoldet. Sie ist etwas leichter als die anderen. Kann man mit einer einfachen Balkenwaage durch zwei Wägungen herausfinden, welche die gefälschte Münze ist?

Herleitung

Man könnte zunächst denken, daß der Auswahl von einer aus acht Münzen einer Information von ld 8 = 3 bit entspräche und man dafür drei Wägungen benötigte, bei denen man für eine erste Wägung auf jede Waagschale je vier Münzen legt. Die leichtere Vierergruppe könnte man dann für eine zweite Wägung in zwei Zweiergruppen aufteilen. Schließlich wäre aber eine dritte Wägung nötig, um als der leichteren Zweiergruppe die gesuchte leichtere Münze zu identifizieren. Zwei solcher Wägungen reichen also nicht.

Die obige Frage ist dennoch zu bejahen. Man legt zunächst je drei Münzen auf die beiden Waagschalen, so daß zwei zurückbleiben. Dadurch gibt es drei mögliche Ergebnisse:

Entweder sind beide Dreiergruppen gleichschwer. Dann ist die gefälschte Münze aus der zurückgelegten Zweiergruppe durch eine weitere Wägung zu erkennen.

Oder eine der Dreiergruppen ist leichter als die andere. Dann legt man aus ihr eine Münze zurück. In einer zweiten Wägung mit je einer Münze in den Waagschalen ist dann bei ungleichem Gewicht die gefälschte zu erkennen. Bei gleichem Gewicht ist jedoch die zurückgelegte Münze gefälscht.

Theoretische Analyse

Der Unterschied zwischen beiden Verfahren besteht darin, daß im ersten Verfahren bei fortgesetzter Aufteilung in zwei gleichgroße Teilmengen pro Wägung gemäß der Definition des Bit als Information nur genau ein Bit als Entscheidung zwischen zwei gleichwahrscheinlichen Möglichkeiten ermittelt wird. Zwei derartige Wägungen würden also nicht reichen, die falsche Münze zu identifizieren, da sie zusammen nur 2 bit statt erforderlicher 3 bit liefern.

Im zweiten Verfahren kann bei der ersten Wägung die leichtere Münze je mit der Wahrscheinlichkeit 3/8 in der einen oder der anderen Waagschale oder mit der Wahrscheinlichkeit 2/8 in keiner der beiden liegen.

Diese erste Wägung liefert dann die Information \begin{align} H_1 &= - \sum_{k=1}^3 p_k \log_2(p_k)\\ &=-\left(\frac{3}{8}\log_2\left(\frac{3}{8}\right) +\frac{3}{8}\log_2\left(\frac{3}{8}\right) +\frac{2}{8}\log_2\left(\frac{2}{8}\right)\right)\\ &=-\frac{1}{4}\left( \underbrace{\log_2(2)}_1 -\underbrace{\log_2(8)}_3+3\log_2(3) -3\underbrace{\log_2(8)}_3 \right)\\ &=\frac{1}{4} \left(11-3\log_2(3) \right) \end{align} Die anschließende zweite Wägung entscheidet mit der Wahrscheinlichkeit 2/8 zwischen zwei Möglichkeiten und liefern dabei (2/8) · 1 bit an Information oder zweimal mit je der Wahrscheinlichkeit (3/8) zwischen drei Möglichkeiten. Das ergibt eine Information von 2 · (3/8) ld(3) bit. Die zweite Wägung ergibt also insgesamt die Information \begin{align} H_2 &= \frac{2}{8}\log_2(2) + 2\cdot \frac{3}{8}\log_2(3)\\ &= \frac{1}{4}\left(1+3\log_2(3)\right). \end{align} Durch die erste und die zweite Wägung erhält man als Summe also \begin{align} H &= H_1+H_2\\ &=\frac{1}{4}\left((11+1) - 3\log_2(3) +3\log_2(3)\right)\\ &=3\text{ bit}. \end{align}

Ergebnis:

Zur Ermittlung einer leichteren aus acht sonst gleichen Münzen reichen zwei Wägungen mit einer Balkenwaage, wenn dabei genau die Menge an Information, nämlich 3 bit, gewonnen wird wie bei drei Wägungen von je zwei gleichgroßen Teilmengen.