Das Diplom als Wägemeister konnte glücklicherweise an Herrn Frank Entrich aus Norderstedt (Deutschland) vergeben werden, denn er hat diese Aufgabe als erster vollständig und richtig gelöst, wie die unten von ihm stammende Lösung zeigt. Falls Sie immer noch verzweifelt am Weitergrübeln sind, so wenden Sie sich doch am besten direkt an ihn.
Ich teile die Kugeln in drei Gruppen ein ( mit jeweils vier Kugeln ):
0 0 0 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12
1. Wägeversuch:
Ich wiege die Gruppe 1 und 2 ( Kugeln 1 - 8 )
0000 = 0000 => die Waage befindet sich im Gleichgewicht
1234 5678
=> die ungleiche Kugel befindet sich in der dritten
Gruppe (Kugeln 9 - 12)
2. Wägeversuch:
Ich wiege 3 Kugel aus der dritten Gruppe sowie eine Kugel aus den ersten
acht ( somit bleibt eine Kugel aus der dritten Gruppe weiterhin
unberücksichtigt.)
0 0 = 0 0 => die Waage befindet sich im Gleichgewicht
9 10 11 5
=> die ungleiche Kugel ist die bisher noch nicht
gewogene Kugel
3. Wägeversuch:
Ich wiege die bisher noch nicht gewogene Kugel mit einer bekannten Kugel
(Kugel aus 1 - 11). Je nach dem, wie die Waage ausschlägt, weiß man, ob
sie schwerer oder leichter ist.
0 <> 0 => die Kugel 5 ist bekannt, Gewicht wie die
12 5 anderen Kugeln 1 - 11
oder:
2. Wägeversuch:
Gleiche Wägung wie eben, nur die Waage schlägt zu einer Seite aus.
0 0 <> 0 0 => die Waage befindet sich in einem
9 10 11 5 Ungleichgewicht
=> Somit ist eine der drei Kugeln aus der dritten
Gruppe die ungleiche Kugel. Ich weiß aber aus dieser
Wägung, je nach dem, ob sie sich links senkt und
rechts hebt bzw. umgekehrt, wo die vermeintlich leichte
bzw. schwere Kugel liegt.
3. Wägeversuch:
Annahme: die Waage senkt sich links und hebt sich somit rechts.
Ich wiege die linke Seite gegeneinander ( Kugel 9 mit Kugel 10 )
0 = 0 => die Waage befindet sich im Gleichgewicht
9 10
=> Bezogen auf die Annahme muß die Kugel 11 die
leichte Kugel sein.
oder:
3. Wägeversuch:
Gleiche Annahme !
Aber die Waage befindet sich im Ungleichgewicht.
0 <> 0 => die Waage befindet sich im Ungleichgewicht
9 10
=> Die Seite, wo sich die Waage sich senkt, ist
die Seite mit der Schweren Kugel
oder:
die erste Wägung wirft die Waage schon in ein Ungleichgewicht.
1. Wägeversuch:
0 0 0 0 <> 0 0 0 0 => die Waage ist im
1 2 3 4 5 6 7 8 Ungleichgewicht
=> Somit sind in der dritten Gruppe nur gleiche Kugeln.
2. Wägeversuch:
Annahme: Die Waage senkt sich links und hebt sich rechts im ersten
Versuch.
Ich verteile die Kugeln bei dieser Wägung so, das ich mir das Ergebnis
aus der ersten Wägung zu nutzen mache. Ich sage, links sind die
vermeintliche schweren Kugeln und rechts die vermeintlich leichten
Kugeln ( bezogen auf die Annahme)
s s l l s g => Abkürzung: s = vermeintlich schwer
0 0 0 = 0 0 0 l = vermeintlich leicht
1 2 5 6 3 9 g = Kugel mit bekannten Gewicht
=> die Waage ist im Gleichgewicht
=> die ungleiche Kugel befindet sich zwischen den momentan
nicht betrachteten Kugeln 4 ( s ), 7 ( l ) und 8 ( l ).
3. Wägeversuch:
Jetzt untersuche ich die Kugeln 7 ( l ) und 8 ( l ).
l l
0 = 0 => die Waage befindet sich im Gleichgewicht
7 8
=> Somit muß die Kugel 4 die schwere Kugel sein.
oder :
2. Wägeversuch:
Gleiche Annahme !
Diesmal ist bei der zweiten Wägung die Waage im Ungleichgewicht.
s s l l s g
0 0 0 <> 0 0 0 => die Waage befindet sich im
1 2 5 6 3 9 Ungleichgewicht
=> Somit können es fünf verschiedene Kugeln sein (Kugel
1, 2, 3, 5 oder 6).
Unterscheidung:
1. Die Waage senkt sich links und hebt sich rechts:
Für diesen Fall sind nur die Kugel 1 (s), 2 (s) und 6 (l) relevant.
3. Wägeversuch:
Vergleichswägung zwischen Kugel 1 und 2
s s
0 = 0 => die Waage ist im Gleichgewicht
1 2
=> Somit muß die Kugel 6 die leichte Kugel sein.
oder:
3. Wägeversuch:
Vergleichswägung, nur diesmal mit Ungleichgewicht.
s s
0 <> 0 => die Waage im Ungleichgewicht
1 2
=> die schwerere Kugel liegt dort, wo sich die Waage nach unten neigt.
2. die Waage hebt sich links und senkt sich rechts.
Für diesen Fall sind nur die Kugeln 5 (l) und 3 (s) relevant.
3. Wägung:
Ich wiege die Kugel 5 mit einer bekannten Kugel ab. Wenn die Waage dann
im Gleichgewicht steht, ist die Kugel 3 die schwere Kugel. Steht die
Waage im Ungleichgewicht, so ist die Kugel 5 die leichte Kugel.
Um diese Aufgabe systematisch anpacken zu können, betrachten Sie die Informationsmenge der gesuchten Information: Information, ob die Kugel leichter oder schwerer: 2 Zustände => log2(2) = 1 Bit. Information, welche Kugel: log2(12) = 3,58 Bits => Gesamtinformationsmenge = log2(2) + log2(12) Bits = log2(2·12) = log2(24) Bits, d.h. Sie haben aus einer Menge von 24 Möglichkeiten eine zu bestimmen. Anschliessend betrachten wir noch die Informationsmenge der bei den drei Wägungen gelieferten Informationsmenge: Information, ob leichter, schwerer oder gleich: 3 Zustände => log2(3) = 1,58 Bits => Bei drei Wägungen ergibt sich die Informationsmenge 3·log2(3) Bits = log2(3³) Bits = log2(27) Bits, also sogar noch etwas überflüssige (redundante) Information.
Die eigentliche Lösung lässt sich mit Hilfe eines Streichschemas am einfachsten lösen:
X = kommt nicht mehr in Frage, ? = noch in Frage kommend
111
123456789012 => Kugelnummer
schwerer ????????????
leichter ????????????
Anfänglich ist noch alles möglich. Die folgende erste Wägung ist nun so anzusetzen, dass danach die verbleibende Informationsmenge der beiden übrigen Wägungen in sämtlichen drei Gewichtsfällen noch ausreicht, um die Aufgabe lösen zu können: 2 Wägungen liefern 2·log2(3) Bits = log2(3²) Bits = log2(9) Bits Information. Diese Informationsmenge reicht aus, um exakt einer aus 9 Zuständen bestimmen zu können => d.h. die Situation muss nach dieser ersten Wägung so aussehen, dass nur noch max. 9 ? verbleiben.
Beispiel für falschen Ansatz bei der 1. Wägung: 3 Kugeln auf beide Schalen (Nr. 1 - 3 links, Nr. 4 - 6 rechts):
Fall 1 : links schwerer (>)
111
123456789012
schwerer ???XXXXXXXXX (entweder in 1-3 der schwerere »Aussenseiter«
leichter XXX???XXXXXX oder in 4-6 der leichtere »Aussenseiter«)
Fall 2 : Gleichgewicht (=)
111
123456789012
schwerer XXXXXX?????? (der »Aussenseiter« muss sich in 7-12 befinden, man
leichter XXXXXX?????? weiss aber noch nicht, ob schwerer oder leichter)
Fall 3 : rechts schwerer (<)
111
123456789012
schwerer XXX???XXXXXX (entweder in 1-3 der leichtere »Aussenseiter«
leichter ???XXXXXXXXX oder in 4-6 der schwerere »Aussenseiter«)
In den Fällen 1 und 3 konnten 18 dieser 24 in Frage kommenden Möglichkeiten gestrichen werden, so dass nur noch einer aus 6 Zuständen bestimmt werden muss [log2(6) Bits Information nötig], wofür diese log2(9) Bits Information der beiden verbleibenden Wägungen noch ausreichen. Bei Fall 2 konnten jedoch nur 12 Möglichkeiten gestrichen werden, so dass immer noch 12 in Frage kommende Möglichkeiten verbleiben, wofür log2(12) Bits Information noch nötig wären => diese log2(9) Bits an Informationen der beiden verbleibenden Wägungen reichen nicht mehr aus, um das in der Aufgabe Verlangte bestimmen zu können. Gerade mit Fall 2 muss hier genauso gerechnet werden, denn das Problem soll sich ohne Glückspieltaktik lösen lassen. Die folgende Tabelle zeigt fallbezogen, was noch übrigbleibt.
| Anz. Kugeln pro Schale | Fall > | Fall = | Fall < |
|---|---|---|---|
| 1 | 2 | 20 (>9!) | 2 |
| 2 | 4 | 16 (>9!) | 4 |
| 3 | 6 | 12 (>9!) | 6 |
| 4 | 8 | 8 | 8 |
| 5 | 10 (>9!) | 4 | 10 (>9!) |
| 6 | 12 (>9!) | 0 | 12 (>9!) |
Die obige Tabelle zeigt klar, dass nur mit dem Fall, je 4 Kugeln auf jeder Seite, weitergearbeitet werden kann. Der richtige Ansatz mit je 4 Kugeln auf jeder Seite (Nr. 1 - 4 links, Nr. 5 - 8 rechts) ergibt folgende Situationen:
Fall 1 : links schwerer (>)
111
123456789012
schwerer ????XXXXXXXX (entweder in 1-4 der schwerere »Aussenseiter«
leichter XXXX????XXXX oder in 5-8 der leichtere »Aussenseiter«)
Fall 2 : Gleichgewicht (=)
111
123456789012
schwerer XXXXXXXX???? (der »Aussenseiter« muss sich in 9-12 befinden, man
leichter XXXXXXXX???? weiss aber noch nicht, ob schwerer oder leichter)
Fall 3 : rechts schwerer (<)
111
123456789012
schwerer XXXX????XXXX (entweder in 1-4 der leichtere »Aussenseiter«
leichter ????XXXXXXXX oder in 5-8 der schwerere »Aussenseiter«)
Bei allen drei Fällen können je 16 Möglichkeiten gestrichen werden, so dass eine Fortsetzung immer möglich ist. Bei der zweiten Wägung setzt man denselben Vorgang derart fort, dass nur noch max. je 3 Möglichkeiten übrigbleiben (3 Fälle bei der ersten Wägung × 3 Fälle 2. Wägung = total 9 Streichdiagramme!), da dort nur noch je log2(3) Bits Informationen verbleiben.
Wieder zur Aufgabenstellung zurück