Schiebepuzzle < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ein Schiebepuzzle besteht aus 15 nummerierten Teilen in einem 4x4-Quadrat, wobei ein Feld frei bleibt. Benachbarte Teile können senkrecht oder waagrecht in das freie Feld verschoben werden. Ein Schiebepuzzle heißt lösbar, wenn es durch eine endliche Folge Verschiebungen in die Zielposition (A) überführt werden kann.
Betrachten Sie bei dieser Aufgabe, die möglichen Positionen des Puzzles als Permutationen in [mm] S_{16}, [/mm] indem Sie die Zahlen von links oben nach rechts unten lesen und das freie Feld mit 16 bezeichnen. Die Zielposition (A) ist also gerade die Identität in [mm] S_{16}.
[/mm]
A:= [mm] \pmat{ 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & \ldots }
[/mm]
Sei B:= [mm] \pmat{ 6 & 11 & 1 & 2 \\ 3 & 4 & 5 & 7 \\ 8 & 10 & 12 & 13 \\ 14 & 15 & 9 & \ldots } [/mm] die Ausgangsposition eines Schiebepuzzles.
a) Berechnen Sie das Signum von B
b) Zeigen Sie, dass jeder mögliche Spielzug das Signum der Spielposition verändert
c) Zeigen Sie, dass es unmöglich ist, von B aus die Zielposition A zu erreichen |
Hallo,
zu a) erst mal: B = (1 6 4 2 11 12 13 14 15 9 8 7 5 3 )= (1 6)(4 6)(2 4)(2 11)(11 12)(12 13)(13 14)(14 15)(9 15)(8 9)(7 8)(5 7)(3 5)
[mm] \Rightarrow [/mm] sgn(B) = [mm] (-1)^{13}= [/mm] -1, da jede Transposition Signum -1 hat.
Zur b) und c) fällt mir leider nich wirklich etwas ein, außer dass ich mir nich vorstellen kann, dass man wirklich jeden einzelnen möglichen Zug durchgehen muss.
Wäre wirklich sehr dankbar, wenn jemand helfen könnte, um mich mal auf eine Idee bei b) und c) zu bringen.
Viele Grüße
|
|
| |
|
Hallo,
zur b) kam mir noch folgende Idee: Eine Verschiebung entspricht doch B verknüpft mit einer Transposition. K Verschiebungen entsprechen B verknüpft mit K Transposition. Da jedoch jede einzelne Transposition das Signum -1 hat, muss sich das Signum durch jeden möglichen Spielzug logischerweise ändern.
Ist das so richtig?
Bei der c) weiß ich allerdings immer noch nich, wie ich weiterkommen soll?
Hoffe ihr könnt mir doch noch weiterhelfen,
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 So 24.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Sa 23.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Man kann wohl leicht zeigen, dass eine gerade Anzahl
von Zügen nötig ist, um von einer Anordnung zu einer
anderen zu kommen, bei der die Lücke an der gleichen
Stelle ist. Insgesamt bleibt dabei das Signum erhalten,
weil [mm] (-1)^{gerade Zahl}=1 [/mm] . Wenn man nun zeigen kann, dass die
Anordnungen A und B unterschiedliches Signum haben,
so ist man am Ziel.
LG Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:20 Sa 23.05.2009 | | Autor: | ms2008de |
Hallo,
also das Signum von A hab ich ja schon berechnet, das is (-1). Und das Signum von B, also der Identität is 1, das is mir auch klar. Mir ist auch völlig klar, dass ich ausschließlich mit einer geraden Anzahl von Zügen das freie Feld wieder auf die gleiche Position wie bei der Ausgangsposition B bekommen könnte. Das einzige was mir noch völlig unklar ist, wie ich zeige, dass es ausschließlich diese gerade Anzahl von Zügen tut und ich mit einer ungeraden Anzahl von Verschiebungen unmöglich wieder das freie Feld auf die selbe Position wie bei (B) bringen kann? Hätte da vielleicht noch jemand ne Idee zu für mich, bitte?
Viele Grüße
|
|
|
| |
|
> Hallo,
> also das Signum von A hab ich ja schon berechnet, das is
> (-1). Und das Signum von B, also der Identität is 1, das is
> mir auch klar. Mir ist auch völlig klar, dass ich
> ausschließlich mit einer geraden Anzahl von Zügen das freie
> Feld wieder auf die gleiche Position wie bei der
> Ausgangsposition B bekommen könnte. Das einzige was mir
> noch völlig unklar ist, wie ich zeige, dass es
> ausschließlich diese gerade Anzahl von Zügen tut und ich
> mit einer ungeraden Anzahl von Verschiebungen unmöglich
> wieder das freie Feld auf die selbe Position wie bei (B)
> bringen kann? Hätte da vielleicht noch jemand ne Idee zu
> für mich, bitte?
> Viele Grüße
Hallo,
denk' dir eine schachbrettartige schwarz-weiss-Färbung
der 16 Felder des Puzzles. Bei jedem Zug wechselt das
freie Feld von einem weissen auf ein schwarzes Feld oder
umgekehrt. Die Anzahl Züge, um das freie Feld auf seinen
ursprünglichen Platz zurückzubringen, muss deshalb gerade
sein.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:14 Sa 23.05.2009 | | Autor: | ms2008de |
Mir is es ja völlig klar, dass es ne gerade Anzahl sein muss, aber wie man das formal mathematisch korrekt beweisen kann, das is so die Sache, da hab ich keine Ahnung.
Aber vielen Dank für deine Hilfe
|
|
|
| |
|
> Mir is es ja völlig klar, dass es ne gerade Anzahl sein
> muss, aber wie man das formal mathematisch korrekt beweisen
> kann, das is so die Sache, da hab ich keine Ahnung.
> Aber vielen Dank für deine Hilfe
Meiner Ansicht nach ist die Überlegung mit der
Schachbrettfärbung mathematisch korrekt und
fundiert.
Wenn du es lieber rechnerisch hast, so betrachte
das Signum [mm] s:=(-1)^{i+j}, [/mm] wobei (i,j) die Position der Lücke
darstellt. Bei jeder Bewegung der Lücke um einen
Schritt nach rechts, links, oben oder unten wechselt
s das Vorzeichen. Wandert bei einem Lösevorgang
die Lücke einem bestimmten Weg entlang, so kann
sie nur nach einer geraden Anzahl von Schritten ihre
ursprüngliche Position wieder einnehmen, weil
[mm] (-1)^{ungerade Zahl}\not= [/mm] 1 ist.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:42 So 24.05.2009 | | Autor: | ms2008de |
Vielen Dank, das is mir mathematisch wesentlich sympathischer, hast mir sehr geholfen!
Viele Grüße
|
|
|
|
