| Autor |
Beitrag |
    
Carpediem (Carpediem)
Erfahrenes Mitglied
Benutzername: Carpediem
Nummer des Beitrags: 79
Registriert: 09-2003
| | Veröffentlicht am Sonntag, den 12. Oktober, 2003 - 09:54: | 
|
Jede Ecke eines Quadrats hat den Zustand 0 oder 1. Folgende Aktionen sind möglich:
Aktion 1: Eine Ecke ändert den Zustand.
Aktion 2: Zwei benachbarte Ecken ändern den Zustand.
Aktion 3: Zwei diagonal gegenüber liegende Ecken ändern den Zustand.
Wenn man eine Aktion setzt, weiß man nie, welche Ecken den Zustand ändern, das bestimmt der Zufall. Gewonnen hat man, wenn alle Ecken denselben Zustand haben.
Aufgabe: Man finde die kürzeste Abfolge von Aktionen, die bei beliebiger Ausgangsposition immer gewinnt. Dabei ist es egal, ob die letzte Aktion zum Gewinn führt oder bereits eine frühere.
werbungsfriedhof@hotmail.com |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 210
Registriert: 10-2001
| | Veröffentlicht am Montag, den 13. Oktober, 2003 - 09:13: |
|
Hallo Carpediem,
das ist ansich ganz einfach, Du mußt dir nur alle Zustände einmal aufschreiben. Ich habe den Ecken Nummern gegeben und sie nacheinander aufgeschrieben.
Aktion 1: setzt x000, 0x00, 00x0 oder 000x
Aktion 2: setzt xx00, 0xx0, 00xx oder x00x
Aktion 3: setzt x0x0 oder 0x0x
Es gibt 16 Kombinationen:
1234
----
0000
0001
0010
0100
1000
0011 : Aktion 2
0101 : Aktion 3
0110 : Aktion 2
0111 : Aktion 1
1001 : Aktion 2
1010 : Aktion 3
1011 : Aktion 1
1100 : Aktion 2
1101 : Aktion 1
1110 : Aktion 1
1111 - Gewonnen
Bei der ersten Gruppe sollte man zunächst versuchen soviele Ecken wie möglich auf 1 zu setzen, das kann man am besten mit Aktion 2.
Die zweite Gruppe ist in einem Zug gelöst - ich habe die einmal die jeweiligen Aktionen aufgeschrieben.
Es ist also im allgemeinen sehr hilfreich zunächst Aktion 2 (oder 3) auszuführen, bis man in Gruppe 2 ist und dann aufzulösen.
Onkel Murray |
Carpediem (Carpediem)
Erfahrenes Mitglied
Benutzername: Carpediem
Nummer des Beitrags: 84
Registriert: 09-2003
| | Veröffentlicht am Montag, den 13. Oktober, 2003 - 12:57: |
|
Das Problem ist, dass du eine Folge von Aktionen finden musst, die immer funktioniert. D.h. man kann es sich nicht so einfach machen: Wenn ich die Zustände x habe, mache ich die Aktion y. Als Lösung müsste eine Folge der Art 2321... von Aktionen herauskommen, von der man 2 Dinge beweisen kann:
(1) Egal, in welchem der 16 Anfangszustände man startet, irgendwann im Verlauf der Aktionen gibt es einen Gewinn.
(2) Es kann keine kürzere Folge geben, die dasselbe schafft.
werbungsfriedhof@hotmail.com |
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 788
Registriert: 02-2001
| | Veröffentlicht am Montag, den 13. Oktober, 2003 - 17:46: |
|
Hi Carpediem!
Ich habe eine Folge, die relativ kurz ist und bin mir auch relativ sicher, dass es keine kürzere gibt, aber den Beweis dafür habe ich noch nicht.
Ich gehe mal davon aus, dass die beiden trivialen Stellungen (0,0,0,0) und (1,1,1,1) mitverarbeitet werden sollen. Wenn nicht, kann man das erste Folgenglied streichen.
Meine Folge: [2,3,2,3,1,3,2,3]
Für den Korrektheitsbeweis teilen wir alle möglichen Stellungen in vier Klassen ein (x><y):
G = Gewinn (x,x,x,x)
D = Diagonale (x,y,y,x)
H = Hälfte (x,x,y,y) oder (x,y,x,y)
E = Einzeln (x,y,y,y) oder (y,x,y,y) oder (y,y,x,y) oder (y,y,y,x)
Nun braucht man nur zu betrachten, wie welche Klassen je nach Aktion ineinander überführt werden:
G =(2)=> H
D =(1)=> E
D =(2)=> H
D =(3)=> G
H =(1)=> E
H =(2)=> D oder G
H =(3)=> H
E =(1)=> H oder D oder G
E =(2)=> E
E =(3)=> E
Nun kann man leicht testen, ob man mit meiner Folge jedes Mal gewinnt:
Ich kürze G =(2)=> H durch G2H ab usw.
[G2H3H2D3G] oder [G2H3H2G]
[D2H3H2D3G] oder [D2H3H2G]
[H2G] oder [H2D3G]
[E2E3E2E3E1G] oder [E2E3E2E3E1H3H2G] oder [E2E3E2E3E1H3H2D3G] oder [E2E3E2E3E1D3G]
Ich denke mal, das waren alle Fälle.
MfG
Martin |
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 789
Registriert: 02-2001
| | Veröffentlicht am Montag, den 13. Oktober, 2003 - 18:20: |
|
Nachtrag:
Mein PC meint, es wäre die kürzeste Folge, weil er keine 6-elementige, dafür aber genau eine 7-elementige Folge findet, die aus jeder Stellung heraus gewinnt außer aus G selbst.
Erweitert man diese Minimalfolge um eine 2 am Anfang, so erhält man eine Folge, die dasselbe kann wie vorher und zusätzlich auch G verarbeiten kann.
Das wär's also, wenn ich mich nicht vertan habe.
MfG
Martin
|
Carpediem (Carpediem)
Erfahrenes Mitglied
Benutzername: Carpediem
Nummer des Beitrags: 87
Registriert: 09-2003
| | Veröffentlicht am Montag, den 13. Oktober, 2003 - 18:23: |
|
Toll. Die Idee mit der Klasseneinteilung hat dich zum Erfolg geführt. Vor allem, dass du zum Unterschied von mir die 3mal0 und 1mal0 Zustände zusammen in eine Klasse gibst, vereinfacht die Sache ungemein. Jetzt muss ich nur noch widerlegen, dass es mit weniger Zügen geht.
Danke,
Martin
werbungsfriedhof@hotmail.com |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 211
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 13:16: |
|
@martin:
Deine Gruppierung für D und H verstehe ich nicht.
Sicherlich ist klar, das z.B. durch deine Wahl von D die Aktion 2 (Diagonale) immer zu H führt.
Aber wieso hast Du das so ausgewählt? Wie kommst du da drauf?
Onkel Murray, steht auf der Leitung
|
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 212
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 13:21: |
|
@martin:
Achja, und 0,0,0,0 ist kein Gewinn, laut Deiner Aufstellung aber schon - wenn Du nur sagst x <> y.
Onkel Murray |
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 790
Registriert: 02-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 13:32: |
|
@Murray:
Siehe Aufgabenstellung:
Gewonnen hat man, wenn alle Ecken denselben Zustand haben.
Mehr war nicht gefordert...
MfG
Martin
|
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 791
Registriert: 02-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 13:42: |
|
Wie ich darauf komme?
Ich habe etwas herumprobiert und versucht, zusammenzufassen. Dabei ist mir aufgefallen, dass es nur eine einzige Stellungsart gibt, bei der man vorher weiß, dass man beim nächsten Zug gewinnt. Also bei D mit 3.
Dann habe ich mir überlegt, wie ich es schaffe, die anderen möglichen Stellungen in D zu überführen. Da jede Klasse einen eigenen Weg benötigt, musste ich "untersuchen", wie sich jeweils die anderen Klassen verhalten, wenn man den Lösungsweg für eine Klasse auf sie loslässt.
Da ist es z.B. sehr hilfreich, dass die Aktionen 2 und 3 den Zustand E invariant lassen.
Zwar kann es sein, dass aus einer Eins und drei Nullen eine Null und drei Einsen werden, aber da sowohl (0,0,0,0) als auch (1,1,1,1) gewinnen, sind beide Zustände gleichwertig und können zu derselben Klasse gezählt werden.
Aber es wäre interessant mal zu sehen, wie (ob?) die Aufgabe bei (1,1,1,1) als einziger Gewinnstellung zu lösen wäre...
MfG
Martin |
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 793
Registriert: 02-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 14:08: |
|
Wo wir gerade dabei sind:
Ich bin mir jetzt sicher, dass es keine Lösung gibt, wenn man nur (1,1,1,1) als Gewinnstellung akzeptiert...
MfG
Martin |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 213
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 14:49: |
|
@Martin:
Ich glaube Du hast Dich beim Aufschreiben vertan und das ist es was mich so verwirrt.
Ich denke, richtig ist:
D = Diagonale (x,y,x,y)
H = Hälfte (x,x,y,y) oder (x,y,y,x)
Denn nur dann führt D3 immer zu G.
Ich hab auch eine Idee wie man das beweisen kann, wenn es der kürzeste Weg ist.
Man baut einen Graphen G auf, der alle Wege von und zu Deinen Gruppierungen enthält. Dann sucht man sich mit Breitensuche den kürzesten Pfad. Da dieses Verfahren schon bewiesen ist, braucht man nur noch den Graphen zu begründen.
Ich glaub ich probier das heute zuhause mal aus :-)
Onkel Murray
|
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 794
Registriert: 02-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 14:59: |
|
Achsooooo!
Da haben wir einfach nur aneinander vorbeigeredet. Denn ich habe die Ecken wohl anders gewählt als du. Bei mir steht (a,b,c,d) für:
a b
c d
Also ist die Schreibweise (x,y,y,x) für D bei mir richtig, denn sie steht für:
x y
y x
Das mit dem Graphen wird wahrscheinlich richtig sein. Ich habe mir schon gestern einen gezeichnet, aber ich wusste irgendwie nicht weiter, denn mein Problem ist, dass ich vier verschiedene Pfade (je nach Anfangsstellung) betrachten muss, die alle durch dieselbe Folge zustande kommen.
Lass mich hier wissen, wenn du etwas hast.
MfG
Martin
|
Carpediem (Carpediem)
Erfahrenes Mitglied
Benutzername: Carpediem
Nummer des Beitrags: 92
Registriert: 09-2003
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 16:17: |
|
Zur Klarstellung:
Es sind ausdrücklich sowohl 0000 als auch 1111 als "Ziel" definiert.
Dank an Martin und Murray für die vielen Gedanken, die ihr euch macht.
werbungsfriedhof@hotmail.com |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 214
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 16:25: |
|
Wir denken noch, schließlich steht der Beweis noch aus ... aber ich bin nah dran. Ist etwas Schreibarbeit, aber ich veröffentliche es sobald ich es habe.
Onkel Murray |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 215
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 17:14: |
|
Nu ham wir es hoffentlich. Eins vorne Weg, ich betrachte das Ändern der Zustände als XOR (Exklusiv-Oder) und zähle die Ecken im Uhrzeigersinn - daher wäre eine Abweichung zu Marins Ergebnis möglich.
Gruppen
=======
E = 1000, 0100, 0010, 0001, 0111, 1011, 1101, 1110
D = 1010, 0101
H = 1100, 0110, 0011, 1001
G = 0000, 1111
XOR Masken
==========
Aktion 1 = 1000, 0100, 0010, 0001
Aktion 2 = 1100, 0110 (0011, 1001 nicht nötig wegen Symetrie)
Aktion 3 = 1010, 0101
Gruppenübergänge
================
E1 => G (Bsp.: 1000 ^ 1000 = 0000)
E1 => D (Bsp.: 1000 ^ 0010 = 1010)
E1 => H (Bsp.: 1000 ^ 0100 = 1100)
E2 => E (Bsp.: 1000 ^ 1100 = 0100)
E2 => E (Bsp.: 1000 ^ 0110 = 1110)
E3 => E (Bsp.: 1000 ^ 1010 = 0010)
E3 => E (Bsp.: 1000 ^ 0101 = 1101)
H1 => E (Bsp.: 1100 ^ 1000 = 0100)
H2 => G (Bsp.: 1100 ^ 1100 = 0000)
H2 => D (Bsp.: 1100 ^ 0110 = 1010)
H3 => H (Bsp.: 1100 ^ 1010 = 0110)
H3 => H (Bsp.: 1100 ^ 0101 = 1001)
D1 => E (Bsp.: 1010 ^ 1000 = 0010)
D2 => H (Bsp.: 1010 ^ 1100 = 0110)
D2 => H (Bsp.: 1010 ^ 0110 = 1100)
D3 => G (Bsp.: 1010 ^ 1010 = 0000)
D3 => G (Bsp.: 1010 ^ 0101 = 1111)
Schritte zur Lösung
===================
Start = E:
E1 => G
E1 => D3 => G
E1 => D2 => H2 => G
E1 => D2 => H2 => D3 => G
E1 => H2 => G
E1 => H2 => D3 => G
E2, E3 sinnlos wegen Schleife zu E
Start = H:
H1 => E
H2 => G
H2 => D3 => G
H3 sinnlos wegen Schleife zu H
Start = D:
D1 => E
D2 => H2 => G
D2 => H2 => D3 => G
D3 => G
Schritt 1 (eindeutig bleibt nur Aktion 3)
---------
E1 => G
E1 => D, H
H1 => E
D1 => E
Das würde bedeuten um im zweiten Schritt das E aufzulösen müßte man wieder Aktion 1 ausführen,
was bei D und H aber wieder zu E führt - eine Schleife!.
E2 => E
H2 => D
D2 => H
Das würde bedeuten um im zweiten Schritt das E aufzulösen müßte man Aktion 1 ausführen,
was bei D und H aber wieder zu E führt - eine Schleife!.
E3 => E
H3 => H
D3 => G
Da D3 direkt zum Gewinn führt beschränkt sich das Problem im Schritt 2 nur noch auf E und H.
Nun geht wegen E nur Aktion 1 im ersten Zug, und das reduziert Anfänge von D und H auf E.
Im zweiten Schritt führt E1 immer zu
Schritt 2 (eindeutig bleibt nur Aktion 2)
---------
E1 => D, H
H1 => E
E1 kann zu H führen, also in eine Schleife (H,E) - dieser Schritt wäre nicht eindeutig.
E2 => E
H2 => D
E ändert sich zwar nicht, aber H wird in D überführt, das im nächsten Schritt eine Lösung bietet.
E3 => E
H3 => H
Aktion 3 ändert hier nichts, wir bleiben also in einer Schleife.
Schritt 3 (Sinn macht nur Aktion 3)
---------
E3 => E
D3 => G
So bleibt nun nur noch E aufzulösen - hier geht daher nur Aktion 1.
Schritt 4 (Sinn macht nur Aktion 1)
---------
E1 => G
E1 => D
E1 => H
Schritt 5 (Sinn macht nur Aktion 3)
---------
Aktion 1 führt zu Schleife mit E.
Aktion 2 führt H in D und D in H über, verlängert also nur unnötig.
Aktion 3 löst D sofort auf und führt H in eine Wiederholung - Vorteil, man brauch nur noch H zu betrachten.
D3 => G
H3 => H
Schritt 6 (Sinn macht nur Aktion 2)
---------
Aktion 1 führt zu Schleife mit E.
Aktion 3 führt zu Schleife mit H.
H2 => D
Schritt 7 (Sinn macht nur Aktion 3)
---------
Aktion 3 zwingend.
D3 => G
Zusammenfassung
---------------
Schritt 1 == 3
Schritt 2 == 2
Schritt 3 == 3
Schritt 4 == 1
Schritt 5 == 3
Schritt 6 == 2
Schritt 7 == 3
Na hoffentlich hab ich mich nicht vertan ... :-)
Onkel Murray |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 216
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 14. Oktober, 2003 - 17:19: |
|
Nachtrag:
Weder eine Breiten-, noch eine Tiefensuche hätte in dem Graphen eine Lösung gebracht, da Schleifen (hier über E) für die Lösung notwendig sind.
Onkel Murray |
Carpediem (Carpediem)
Erfahrenes Mitglied
Benutzername: Carpediem
Nummer des Beitrags: 94
Registriert: 09-2003
| | Veröffentlicht am Donnerstag, den 16. Oktober, 2003 - 01:16: |
|
Wow, super Murray. Jetzt habe ich keinen Zweifel mehr, dass es die kürzeste Lösung ist.
Vielen Dank!  |
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 217
Registriert: 10-2001
| | Veröffentlicht am Donnerstag, den 16. Oktober, 2003 - 10:14: |
|
Achja, und weil es leicht zu ergänzen ist, hier noch der Beweis das es nur für 1111 als Gewinn keine Lösung geben kann.
Gruppen
=======
E = 1000, 0100, 0010, 0001, 0111, 1011, 1101, 1110
D = 1010, 0101
H = 1100, 0110, 0011, 1001
W = 0000
G = 1111
XOR Masken
==========
Aktion 1 = 1000, 0100, 0010, 0001
Aktion 2 = 1100, 0110 (0011, 1001 nicht nötig wegen Symetrie)
Aktion 3 = 1010, 0101
Gruppenübergänge
================
E1 => W (Bsp.: 1000 ^ 1000 = 0000)
E1 => G (Bsp.: 0111 ^ 1000 = 1111)
E1 => D (Bsp.: 1000 ^ 0010 = 1010)
E1 => H (Bsp.: 1000 ^ 0100 = 1100)
E2 => E (Bsp.: 1000 ^ 1100 = 0100)
E2 => E (Bsp.: 1000 ^ 0110 = 1110)
E3 => E (Bsp.: 1000 ^ 1010 = 0010)
E3 => E (Bsp.: 1000 ^ 0101 = 1101)
H1 => E (Bsp.: 1100 ^ 1000 = 0100)
H2 => W (Bsp.: 1100 ^ 1100 = 0000)
H2 => G (Bsp.: 0011 ^ 1100 = 1111)
H2 => D (Bsp.: 1100 ^ 0110 = 1010)
H3 => H (Bsp.: 1100 ^ 1010 = 0110)
H3 => H (Bsp.: 1100 ^ 0101 = 1001)
D1 => E (Bsp.: 1010 ^ 1000 = 0010)
D2 => H (Bsp.: 1010 ^ 1100 = 0110)
D2 => H (Bsp.: 1010 ^ 0110 = 1100)
D3 => W (Bsp.: 1010 ^ 1010 = 0000)
D3 => G (Bsp.: 1010 ^ 0101 = 1111)
W1 => E (Bsp.: 0000 ^ 1000 = 1000)
W2 => H (Bsp.: 0000 ^ 1100 = 1100)
W3 => D (Bsp.: 0000 ^ 1010 = 1010)
Schritte zur Lösung
===================
Schritt 1
---------
Aktion 1: mögliche Scheife H,E,H,...
Aktion 2: H wird zu D und D zu H
Aktion 3: mögliche Scheife D,W,D,...
Es gibt keine Eindeutige Lösung.
q.e.d.
|
|
