denk mal - Auswertungen des Wettbewerbs 2001

>
DENK m a l
+ + + 2001: des Rätsels Lösung + + +

Lösung der 7. vom 9.4.2001

Vorbemerkung:

Auch wenn es einige Mitstreiter nicht glauben konnten, es funktioniert !

Und es lässt sich eindeutig ermitteln ob das Ei leichter oder schwerer ist.

zum Beispiel die Lösung von Roland Spindler: als Fallunterscheidung:

1. Waegevorgang: 13 links und 13 rechts
Fall A: Die beiden Seiten sind gleich schwer
=> eines der restlichen 13 Eier ist leichter oder schwerer
- 2. Waegevorgang: 5 (von den 13) links und 4 (von den 13) + 1 richtiges rechts
  Fall A: Die beiden Seiten sind gleich schwer
  => eines der restlichen 4 Eier ist leichter oder schwerer
  - 3. Waegevorgang: 3 von den 4 links und 3 richtige rechts
    
    Fall A: Die beiden Seiten sind gleich schwer
    Das verbleibende Ei wird mit einem richtigen verglichen
    Fertig!
    Fall B+C: Eine Seite ist schwerer
    Zwei der Eier links werden miteinander verglichen
    Fertig!
  Fall B: Die linke Seite ist schwerer
  => eines der linken 5 ist schwerer oder eines der rechten 4 ist leichter
  - 3. Waegevorgang: Zuerst das richtige Ei entfernen, dann 1 von links und 2 von rechts zur Seite legen, dann 2 von links nach rechts legen und 1 von rechts nach links.
    
    Fall A: Die beiden Seiten sind gleich schwer
    Von den zur Seite gelegten Eiern die beiden von rechts vergleichen
    Fertig!
    Fall B: Die linke Seite ist schwerer
    Von den liegen gebliebenen Eiern die beiden von links vergleichen
    Fertig!
    Fall C: Die rechte Seite ist schwerer
    Von den umgelegten Eiern die beiden von links nach rechts
    gelegten vergleichen
    Fertig!
  Fall C: Die rechte Seite ist schwerer
  => eines der linken 5 ist leichter oder eines der rechten 4 ist schwerer
  (funktioniert analog zu Fall B)
Fall B: Die linke Seite ist schwerer
=> eines der linken 13 ist schwerer oder eines der rechten 13 ist leichter
- 2. Wägevorgang: 6 von links und 3 von rechts zur Seite legen, dann 3 von links nach rechts legen und 5 von rechts nach links, es bleiben also 4 Eier links und 5 rechts liegen, dann noch rechts ein richtiges Ei dazu, damit es gleich viele sind.
  Fall A: Die beiden Seiten sind gleich schwer
  => Eines der 6 weggelegten ist schwerer oder eines der 3 leichter
  - 3. Waegevorgang: 2 eventuell schwerere Eier und 1 ev. leichteres auf der Seite lassen, 2 ev. schwerere nach links und 2 nach rechts, 1 ev. leichteres nach links und 1 nach rechts.
    Fall A: Die beiden Seiten sind gleich schwer
    Die beiden weggelassenen ev. schwereren Eier vergleichen
    Fertig!
    Fall B: Die linke Seite ist schwerer
    Die beiden ev. schwereren Eier links vergleichen
    Fertig!
    Fall C: Die rechte Seite ist schwerer
    Die beiden ev. schwereren Eier rechts vergleichen
    Fertig!
  Fall B: Die linke Seite ist schwerer
  => Eines der 4 liegengebliebenen ist schwerer oder eines der 5 leichter
  - 3. Wägevorgang: 3 eventuell leichtere Eier auf der Seite lassen, 2 ev. schwerere nach links und 2 nach rechts, 1 ev. leichteres nach links und 1 nach rechts.
    Fall A: Die beiden Seiten sind gleich schwer
    Zwei der weggelassenen ev. leichteren Eier vergleichen
    Fertig!
    Fall B: Die linke Seite ist schwerer
    Die beiden ev. schwereren Eier links vergleichen
    Fertig!
    Fall C: Die rechte Seite ist schwerer
    Die beiden ev. schwereren Eier rechts vergleichen
    Fertig!
  Fall C: Die rechte Seite ist schwerer
  => Eines der 3 umgelegten ist schwerer oder eines der 5 leichter
  - 3. Waegevorgang: 1 eventuell schwereres Ei und 1 ev. leichteres auf der Seite lassen, 1 ev. schwereres nach links und 1 nach rechts, 2 ev. leichtere nach links und 2 nach rechts.
    Fall A: Die beiden Seiten sind gleich schwer
    Das weggelassene ev. schwerere mit einem richtigen Ei vergleichen
    Fertig!
    Fall B: Die linke Seite ist schwerer
    Die beiden ev. leichteren Eier rechts vergleichen
    Fertig!
    Fall C: Die rechte Seite ist schwerer
    Die beiden ev. leichteren Eier links vergleichen
    Fertig!
Fall C: Die rechte Seite ist schwerer
=> eines der linken 13 ist leichter oder eines der rechten 13 ist schwerer
(funktioniert analog zu Fall B)

Roland Koppenberger geht der Ostereierwägung auf den Grund

Du hast da wieder mal ein berühmtes Problem ausgegraben (oder an deine Aufgabe vom 15.9.1997 angeknüpft?), das 1945 plötzlich als das "Odd-Ball-Problem" auftauchte (12 Kugeln mit dreimaligem Wägen). Es gibt dazu eine Reihe vorzüglicher Besprechungen.

STRONG, L. C.: How to make an aerodynamic smoke tunnel and more about the puzzle of the 12 balls. In: Scientific American (192) 5. May 1995. pp. 121.
KELLOGG, Paul J. and Dorothy J.: Entropy of Information and the Odd Ball Problem. In: Journal of Applied Physics. Nov. 1954.
GARDNER, Martin: Mathematisches Labyrinth. S. 104 ff. (= Kapitel 11. Das Ternärsystem)

STRONG streift im Zuge der Diskussion des 12-Kugel-Problems eine Reihe von Lösungsansätzen und zeigt praktikable Lösungsalgorithmen und -techniken. Er verweist darunter auch auf KELLOG, wo der thermodynamische Entropiebegriff mit der Informationstheorie verwoben wird, um über Wahrscheinlichkeiten zu einer schnellen Lösung zu gelangen.
GARDNER, der auch jahrelang für den Scientific American Kolumnen schrieb und daraus eine Reihe Bücher destillierte (u.a. dieses), bespricht das Wägeproblem (eng an STRONG orientiert) in Verbindung mit dem Ternärsystem.
Darüberhinaus stellt er noch eine recht simple Lösungsmöglichkeit (für 12 Kugeln und dreimaligem Wägen) vor, die mir persönlich am besten gefällt und die ich im folgenden auch besprechen möchte (sie lässt sich leicht verallgemeinern).

Zunächst eine Vorbemerkung zum Zusammenhang zwischen der Anzahl der Wägungen und der Anzahl der Bälle:

Mit n Wägungen kann ein Ball (mit unterschiedlichem Gewicht in bezug auf jeden anderen Ball) aus Bällen herausgefunden werden.

Mit vier Wägungen können daher 39 Bälle untersucht werden (wie in der aktuellen Denkmal-Aufgabe).

Meine Lieblingslösung:

Zuerst werden alle Bälle von 1 bis 39 durchnumeriert. Da es um Wägen mit einer Balkenwaage geht (drei mögliche Zustände: links schwerer, gleich, rechts schwerer), bietet sich wiederum (wie in der dritten Aufgabe des heurigen Jahres) das Ternärsystem(₃) als Beschreibung an. Übersetzen wir zunächst die Zahlen der Kugeln ins (gewöhnliche) Ternärsystem (Spalte T1). Nun transformieren wir die Ternärzahlen insofern, als wir statt jeder 0 eine 2 und statt jeder 2 eine 0 schreiben (Spalte T2). Jede Kugel hat nun eindeutig zwei Ternärzahlen (die sich jeweils zu 2222₃ = 80 summieren). Wir wählen für jede Kugel diejenige Ternärzahl der beiden aus, deren erste zwei verschiedene Ziffern (von links gelesen) 01, 12 oder 20 sind und ordnen sie der Kugel für die folgenden Wägungen zu (in der Tabelle rot ausgezeichnet).
Jetzt wird viermal gewogen nach folgendem Prinzip: Bei der ersten Wägung kommen jene 13 Kugeln in die linke Schale (L1), deren erste Ziffer der zugeordneten Ternärzahl (von links) eine 0 aufweisen, jene 13 in die rechte Schale mit einer 2 am Anfang (R1). Ist nun die linke Schale schwerer, notieren wir eine 0, ist die rechte schwerer eine 2, bei Gleichstand eine 1. Die zweite Wägung wiegt jene Kugeln, deren zweite Ziffer eine 0 bzw. 2 aufweist (L2 bzw. R2) usw. Das Ergebnis notieren wir wieder wie beim ersten Mal.
Schließlich erhält man eine vierstellige Ternärzahl. Befindet sich diese Zahl in der den Kugeln zugeordneten Ternärzahlen (rot ausgezeichnet), dann ist diese Kugel schwerer. Andernfalls befindet sich die Zahl in den nicht zugeordneten Ternärzahlen, diese Kugel ist dann leichter.

Das mag nun alles recht verwirrend klingen. Ich werde das übersichtlich in einer Tabelle darstellen und anschließend ein Beispiel dazu besprechen.

Kugel
T1 T2 L1 R1 L2 R2 L3 R3 L4 R4

1 0001 2221 1 1 1

2 0002 2220 2 2 2 2

3 0010 2212 3 3 3

4 0011 2211 4 4

5 0012 2210 5 5 5

6 0020 2202 6 6 6 6

7 0021 2201 7 7 7

8 0022 2200 8 8 8 8

9 0100 2122 9 9 9

10 0101 2121 10 10

11 0102 2120 11 11 11

12 0110 2112 12 12

13 0111 2111 13

14 0112 2110 14 14

15 0120 2102 15 15 15

16 0121 2101 16 16

17 0122 2100 17 17 17

18 0200 2022 18 18 18 18

19 0201 2021 19 19 19

20 0202 2020 20 20 20 20

21 0210 2012 21 21 21

22 0211 2011 22 22

23 0212 2010 23 23 23

24 0220 2002 24 24 24 24

25 0221 2001 25 25 25

26 0222 2000 26 26 26 26

27 1000 1222 27 27 27

28 1001 1221 28 28

29 1002 1220 29 29 29

30 1010 1212 30 30

31 1011 1211 31

32 1012 1210 32 32

33 1020 1202 33 33 33

34 1021 1201 34 34

35 1022 1200 35 35 35

36 1100 1122 36 36

37 1101 1121 37

38 1102 1120 38 38

39 1110 1112 39

Ein Beispiel:

Angenommen, Kugel Nummer 17 ist leichter. Die vier Wägungen ergeben folgendes:

Die rechte Schale ist schwerer, wir notieren 2.
Beide Schalen sind im Gleichgewicht, wir notieren 1.
Die linke Schale ist schwerer, wir notieren 0.
Die linke Schale ist schwerer, wir notieren 0.

Wir erhalten als Ergebnis die Ternärzahl 2100₃ und finden sie in der Zeile der Kugel Nummer 17.
2100₃ befindet sich nicht unter den den Kugeln zugeordneten (roten) Ternärahlen, sondern ist eine der schwarzen, also ist Kugel Nummer 17 leichter.

Für alle, deren Hobby es nun geworden ist, von 39 Kugeln (oder Eiern) eine spezielle herauszufinden, hat Jörg Wiegels auf seiner Seite ein System vorbereitet.

Auswertung:

eingegangene Lösungen	richtige Lösungen	falsche Lösungen
31	24	7
Bemerkungen	Diese Aufgabe war wirklich sehr komplex und erschwerend kam noch hinzu, dass es nicht ausreichte nur das gesuchte Ei zu finden.

[ zur 8. Aufgabe ] [ zur 7. zurück ] [ zur Hall of FAME ]

? ? ? ?

Das ist der ganze Jammer:
die Dummen sind so sicher und die Gescheiten so im Zweifel.

Helmut Schmidt

"blättern"