Schiebespiel < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:17 So 02.01.2011 | | Autor: | Kathinka |
| Aufgabe | Bei dem folgenden Schiebespiel darf auf das jeweils leere Feld eines seiner Nachbarfelder geschoben werden. Kann man auf diese Weise den Übergang von
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 []
zu
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15 []
bewirken? |
Ahoi :)
Die eckigen Klammern geben das leere Feld an, diese kleinen Schiebetafeln kennt man noch aus seiner Kindheit, wo sich dann Bilder wieder zusammensetzen... hoffe ihr wisst, was gemeint ist.
Nun zur Fragestellung: Meiner Meinung nach geht es nicht, von Tafel 1 auf Tafel 2 zu kommen. Man schafft ja Veränderung durch ROTATION bei diesen Tafeln, auf der zweiten Tafel sind jedoch lediglich 1 und 2 VERTAUSCHT. Es müsste noch mindestens ein weiteres Zahlenpaar ebenfalls vertauscht sein, damit die Abbildung so möglich ist.
Ist dieser Gedanke richtig? Und wenn ja, kann man das noch mathematisch unterfüttern? Keine Ahnung wie...
Liebe Grüße, Katja
|
|
| |
|
Hi,
ihr hattet bestimmt gerade Permutationen und Vorzeichen einer Permutation. Jeder Spielzug ist eine Permutation (ein 2er-Zykel). Mit jedem Spielzug verändert sich das Vorzeichen (gerade/ungerade).
Das Spielbrett kann man als eine Matrix 4x4 sich vorstellen, bei der jedes Feld mit 1,2,3,16 durch nummeriert ist.
Daraus lässt sich schließen, ob die Spielsituation lösbar ist oder nicht.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:10 So 02.01.2011 | | Autor: | Kathinka |
Hallöchen,
die Aufgabe bezieht sich leider nicht auf eine aktuelle Vorlesung, deshalb sagt mir Permutation auch nicht (mehr?) sonderlich viel ^^ Mit Hilfe von Wikipedia würde ich nun mal folgendes vermuten:
Das Spiel ist lösbar, wenn ich eine gerade Anzahl an Permutationen/2er-Zykeln durchführe (also z.B. von einem positiven über ein negatives wieder zu einem positiven Vorzeichen gelange, Signum 1).
Die zweite Abbildung kommt jedoch über einen einzigen Tausch (Signum -1) zustande. Es ist deshalb in dieser 4x4 Matrix nicht machbar.
Soweit richtig gedacht?
Hat das was damit zu tun dass es sich um eine 4x4 Matrix (also mit gerader Spalten-Zeilen-Anzahl) handelt? Wäre eine vergleichbare Veränderung, also das Vertauschen nur eines Zahlenpaares, in einer 3x3 Matrix machbar? Oder muss es da auch ein "gerades Vorzeichen" geben?
LG Katja
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:18 So 02.01.2011 | | Autor: | felixf |
Moin!
> Hallöchen,
> die Aufgabe bezieht sich leider nicht auf eine aktuelle
> Vorlesung, deshalb sagt mir Permutation auch nicht (mehr?)
> sonderlich viel ^^ Mit Hilfe von Wikipedia würde ich nun
> mal folgendes vermuten:
>
> Das Spiel ist lösbar, wenn ich eine gerade Anzahl an
> Permutationen/2er-Zykeln durchführe (also z.B. von einem
> positiven über ein negatives wieder zu einem positiven
> Vorzeichen gelange, Signum 1).
Das muesste man beweisen.
Was viel einfacher ist: wenn das loesbar ist, so muss die Permutation Signum 1 haben.
Und zwar deshalb:
Die Permutation ist ja ein Produkt von Transpositionen. Jede Transposition hat Signum -1. Es reicht also zu zeigen, dass es eine gerade Anzahl von Transpositionen geben muss. Dazu ueberlegt man sich, dass jede Transposition einer Verschiebung des Punktes entspricht. Und zwar verschiebt sich der Punkt entweder in horizontaler oder vertikaler Richtung. Wenn er nach oben geschoben wird, muss er irgendwann wieder nach unten geschoben werden. Wird er nach links geschoben, muss er irgendwann wieder nach rechts geschoben werden. Ansonsten kann er nicht zum Start zurueckkehren. Da er wieder zurueckkehrt, muss es also eine gerade Anzahl von Verschiebungen gegeben haben. (Und zwar sowohl die Anzahl der Verschiebungen nach Links/Rechts ist gerade, sowie die Anzahl der Verschiebungen nach oben/unten.)
> Die zweite Abbildung kommt jedoch über einen einzigen
> Tausch (Signum -1) zustande. Es ist deshalb in dieser 4x4
> Matrix nicht machbar.
Das hat nichts damit zu tun, dass es eine $4 [mm] \times [/mm] 4$-Matrix ist.
> Soweit richtig gedacht?
> Hat das was damit zu tun dass es sich um eine 4x4 Matrix
> (also mit gerader Spalten-Zeilen-Anzahl) handelt?
Nein. Bei einer $12398 [mm] \times [/mm] 12381$-Matrix waer es genauso.
> Wäre
> eine vergleichbare Veränderung, also das Vertauschen nur
> eines Zahlenpaares, in einer 3x3 Matrix machbar?
Ebensowenig: da der Punkt wieder zum Ursprung zurueckkehrt (also falls dies die Bedingung ist), dann muss das Signum wie oben argumentiert 1 sein. Und eine Transposition hat Signum -1.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:01 Mo 03.01.2011 | | Autor: | Kathinka |
danke, das ist jetzt soweit klar! die frage kann auch als ganz beantwortet gelten! :) lg katja
|
|
|
|
