02: Apfelwein / Apple Wine

  • Knecht Ruprecht stellt zunächst eine Flasche zur Seite, es bleiben 5 Flaschen übrig. Nun probiert er alle Möglichkeiten durch, drei dieser 5 Flaschen in die Maschine zu stellen. Es gibt 10 Möglichkeiten (5 über 3.) Liefert einmal die Maschine das Ergebnis, dass alle drei Flaschen Apfelwein enthalten, kann er den Vorgang abbrechen und dem Weihnachtsmann eine beliebige der drei Flaschen bringen. Liefert die Maschine bei den 10 Durchläufen nie dieses Ergebnis, weiß er, dass unter den 5 Flaschen keine 3 Flaschen mit Apfelwein sind, also kann er ohne weitere Tests die zur Seite gestellte Flasche dem Weihnachtsmann bringen.

  • Es gibt 2 Möglichkeiten, wie du wissen kannst, dass eine Flasche den guten Wein enthält: Entweder, weil die Glühbirne geleuchtet hat, als die Flasche drin war, oder weil alle verbleibenden ungeprüften Kombinationen die Flasche enthalten und die Lampe noch nicht geleuchtet hat. Wenn du also erst alle 10 Kombinationen versuchst, in denen eine der Flaschen nicht vorkommt, dann hat entweder mal die Lampe geleuchtet - dann kennst du gleich alle 3 Flaschen mit Wein - und du weißt, dass die unbenutzte Flasche Wein enthalten muss.

  • Man könnte die Flaschen mit 1-6 bezeichnen.

    Dann lässt man z.B. die Flasche 6 immer draußen.

    Es ergeben sich 123, 124, 125, 134, 135, 145, 234, 235, 245, 345 als Tests für alle Kombinationen der Flaschen 1-5.

    Spätestens dann hat man entweder einmal die Lampe an - oder aber nie. Im letzteren Fall ist es Flasche 6, die man trinken kann. Prost.

  • Eine obere Grenze ist sehr schnell gefunden. Für 3 Flaschen von 6 gibt es 6 über 3 = 20 Kombinationen. Schlimmstenfalls die letzte zeigt uns Grün, und wir kennen alle guten Flaschen. Auf 19 kann man das auch leicht korrigieren, denn den letzten Test kann man sich offensichtlich sparen.


    Es geht aber noch besser: Wir stellen zuerst eine Flasche (ich nenne sie A) beiseite, und probieren alle Kombinationen der verbleibenden Flaschen aus. Das sind 5 über 3 = 10. Wenn dabei einmal die Lampe Grün leuchtet, haben wir auch alle guten Flaschen gefunden. Wenn nicht, wissen wir aber zumindest, dass A gut sein muss.


    Ist dies nun optimal? Ja.

    Dazu ist zunächst festzustellen, dass der betrachtete „worst case“ IMMER derjenige ist, dass die Lampe Rot leuchtet, denn sonst wären wir sofort fertig (1). [Anmerkung: Diese Tatsache macht die Aufgabe mMn sehr schön, weil man bei ähnlichen Aufgaben oft gefühlt hunderte Varianten betrachten muss, um den worst case zu identifizieren, was sehr langweilig ist.]

    Weiterhin gibt es insgesamt 6 über 3 = 20 Möglichkeiten für die guten Flaschen (2).

    Jede Flasche ist in 5 über 2 = 10 Kombinationen enthalten (man muss 2 aus den 5 verbleibenden wählen) (3).

    Jeder Test schließt nach (1) exakt eine Kombination aus und sonst nichts. Wenn wir nun 9 beliebige Kombinationen testen, sind also nach (2) noch 11 möglich. Nach (3) ist aber keine Flasche in diesen allen enthalten, folglich kann auch keine Flasche sicher gut sein. Damit brauchen wir mindestens 10 Versuche, und dass das auch geht, zeigt der vorherige Absatz. qed