| Thema: Fische in der Zentrifuge |
| Zediccius (15 Beiträge) am 04.05.2009 um 17:32 Uhr: |
In einer Zentrifuge mit 4 Behältern (die vollkommen symetrisch im Quadrat angeordnet und nicht zu unterscheiden sind) sind 4 Fische. Die Fische sind anfangs zufällig mit dem Kopf nach oben oder mit dem Kopf nach unten in jeweils einem der Behälter. Jedesmal wenn die Zentrifuge wegen einer Unwucht anhält, kann man mit jeder Hand einen Behälter öffnen (also zwei Behälter), anschauen welche Orientierung die Fische haben und einen, beide oder keinen Fisch umdrehen. danach läuft die Zentrifuge selbsttätig wieder an, so dass man beim nächsten Mal nicht mehr weiß, welche Behälter man zuvor geöffnet hatte.
Natürlich ist es verboten die Behälter oder Fische zu markieren.
Gesucht wird die minimale Anzahl an Kontrollen und Fischdrehungen um alle Fische gleich zu orientieren und damit einen sicheren Betrieb der Zentrifuge ohne Unwucht zu garantieren.
Glück darf beim Lösungsweg natürlich keine Rolle spielen. Also, Lösungen wie: \'Ich öffne zwei benachbarte Bahälter, drehe beide Fische mit dem Kopf nach oben und wenn ich beim nächsten mal die beiden anderen Behälter erwische hab ichs geschafft\' sind keine Lösungen.
Ein kleines Teufelchen in der Zentrifuge sorgt bei solchen Lösungsvorschlägen leider für ein Worst-Case-Scenario, so dass auch bei beliebig vielen Versuchen nie die beiden verbliebenen Behälter gegriffen werden...
Hmmm, hoffe ich hab mich halbwegs verständlich ausgedrückt...
Viel Spaß
|
| Zivi (4 Beiträge) am 14.05.2009 um 13:39 Uhr: |
K:= Kopf des Fisches zeigt nach oben
O:=Flosse des Fisches zeigt nach oben
Beim ersten Stopp greife ich mir zwei diagonal gegenüberstehende Behälter und drehe die Fische so, dass beide mir dem Kopf nach oben zeigen.
K ?
? K
Sollte die Zentrifuge erneut stoppen, greife ich mir zunächst einen Behälter. Zeigt der Kopf des Fisches nach unten, nehme ich den diagonalgegenüberliegen Behälter und stelle beide Fische mit dem Kopf nach oben und bin fertig!
Ist in dem Behälter ein Fisch der mit dem Kopf nach oben zeigt, greife ich mit einen benachbarten Behälter und drehe den Fisch ggf. mit dem Kopf nach oben. Es zeigen nun mindestens drei Fische mit dem Kopf nach oben.
K ?
K K
Stoppt die Zentrifuge erneut (3. Stopp), muss der letzte Fisch mit dem Kopf nach unten zeigen.
Ich öffen zunächst einen Behälter. Zeigt der Kopf des Fisches nach unten, drehe ich diesen um und bin fertig!
Zeigt der Kopf des Fisches nach oben, nehme ich den nächsten Behälter gegen den Urzeigersinn. Zeigt der Kopf dieses Fisches nach unten, drehe ich diesen um und bin fertig. Zeitg der Kopf nach oben drehe ich diesen um.
Es gibt nun zwei Mögliche Konstellationen in der Zentrifuge:
K O K O
O K K O
Beim nächsten Stopp (4. Stopp) öffne ich zwei diagonal gegenüberliegende Behälter. Liegen die Fische gleich, drehe ich sie beide um und bin fertig. Andernfalls verändere ich nichts, weiß aber, dass die Konstellation wie folgt ist:
K O
K O
Beim nächsten Stopp (5. Stopp) öffne ich zwei nebeneinander liegende Behälter. Liegen beide Fische gleich drehe ich beide um und bin fertig!
Liegen die Fische unterschiedlich, drehe ich auch beide um. Ich habe nun folgende Konstellation:
K O
O K
Beim nächsten Stopp (6. Stopp) drehe ich zwei diagonal gegenüberliegende Fisch um und bin fertig! Ich brauche also maximal 6 Stopps!
Gruß Zivi
Ich habe die Nummerierungen hinzugefügt, es sind wirklich 6. Und ich habe noch einen weiteren Fehler im zweiten Schritt gefunden, hier wird ein möglicher Fall nicht berücksichtigt! Aber die Lösung unten ist ohnehin schöner
|
| Ausblenden Anzeige: |
|
|
| peter (34 Beiträge) am 14.05.2009 um 21:45 Uhr: |
Nette Lösung. Mir fällt jetzt spontan keine bessere Lösung ein.
|
| Zediccius (15 Beiträge) am 14.05.2009 um 22:08 Uhr: |
Schöne Lösung.
Aber wenn ich mich nicht verzählt habe sind das 6 Stopps.
Vielleicht könntest du die Stopps noch durchnummerieren?
Es geht aber auch mit weniger als 6 Stopps und (wenn auch nicht ausdrücklich in der Aufgabenstellung geschrieben) bei jeweils gleichzeitigem Öffnen der Behälter.
An deinen ersten beiden Schritten ist jedoch nichts auszusetzen.
(Wenn man immer vom worst case ausgeht kann man im zweiten Schritt auch direkt benachbarte Behälter nehmen um die 3zu1 Konstellation zu erhalten).
|
| Zivi (4 Beiträge) am 17.05.2009 um 10:10 Uhr: |
OK, dann versuche ich mal ein Update:
K:= Kopf des Fisches zeigt nach oben
O:=Flosse des Fisches zeigt nach oben
Beim ersten Stopp greife ich mir zwei diagonal gegenüberstehende Behälter und drehe die Fische so, dass beide mir dem Kopf nach oben zeigen.
K ?
? K
Sollte die Zentrifuge ein zweites Mal stoppen, muss mindestens ein Fisch mit dem Kopf nach unten zeigen.
Ich öffne zwei nebeneinander liegende Behälter. Zeigt ein Fisch mit dem Kopf nach unten, drehe ich diesen um. Und wir haben volgende Konstellation:
K ?
K K
Zeigen beide Fische mit dem Kopf nach oben, drehe ich beide um. Da die Zentrifuge gestoppt hat, muss noch ein weiterer Fisch nach unten zeigen:
K O
O O
(Möglich wäre auch zunächst einen Behälter zu öffnen und falls der Kopf des Fisches nach unten zeigt, den diagonalgegenüberliegen Behälter zu öffnen. In diesem Fall wäre ich evtl. schon nach dem 2. Schritt fertig.)
Stopp die Zentrifuge ein drittes Mal, gibt es nur zwei Möglichkeiten:
K O K O
K K O O
Da ich durch mein Vorgehen im zweiten Schritt weiß, welche der strukturgleichen Siuationen vorliegt, reicht es eine zu betrachten.
K O
K K
Ich öffne zwei diagonal nebeneinander liegende Behälter. Zeigt ein Fisch mit dem Kopf nach unten, drehe ich diesen um und bin fertig. Andernfalls drehe ich einen der beiden gleich orientierten Fische um und habe folgende Konstellation:
K O
K O
Im vierten Schritt greife ich mir zwei nebeneinander liegende Behälter und drehe beide Fische um. Waren die Fische gleich orientiert, bin ich fertig!
Im fünften Schritt liegt folgende Konstellation vor:
K O
O K
Ich greife mit zwei diagonal gegenüberliegende Behälter und drehe beide Fische um - und bin spätestens im fünften Schritt fertig! :o)
Ich bin nun am fünften Schritten angekommen. Geht es noch schneller?
|
| Zediccius (15 Beiträge) am 18.05.2009 um 08:21 Uhr: |
Deine Lösung ist richtig. Herzlichen Glückwunsch.
Es geht nicht noch schneller. Im schlimmsten Fall hat man alle Fische nach fünf Stopps gleich orientiert.
Es gibt noch eine etwas einfachere Lösung, die jedoch nur die Schritte zwei und drei betrifft (man kann sich dort eine Fallunterscheidung sparen).
Hier noch einmal die Lösung für den worst case:
Schritt 1: man nimmt zwei diagonale Behälter und dreht ggf. die Fische mit dem Kopf nach oben.
K ?
? K
Schritt 2: man öffnet zwei nebeneinander liegende Behälter und dreht ggf. beide Fische mit dem Kopf nach oben.
K K
O K
Schritt 3: man öffnet zwei diagonale Behälter und dreht einen der beiden Fische mit dem Kopf nach unten.
K K
O O
Schritt 4: man öffnet zwei nebeneinander liegende Behälter und dreht beide Fische um.
K O
O K
Schritt 5: man öffnet zwei diagonal liegende Behälter und dreht beide Fische um.
K K
K K oder
O O
O O
|
