\n
\nZasady s\u0105 bardzo proste. Jest 15 kwadratowych klock\u00f3w oraz jedno puste miejsce (nazwijmy je klockiem pustym), kt\u00f3re znajduj\u0105 si\u0119 w kwadratowej planszy o wymiarach 4×4 jak poni\u017cej:<\/p>\n
![\"pi\u0119tnastka\"](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15a_01.png\")
<\/p>\n
\nNazwijmy t\u0119 pozycj\u0119 wyj\u015bciow\u0105 oraz oznaczmy j\u0105 przez \\(P_0\\). Klocki mo\u017cemy jedynie przesuwa\u0107, tj. w puste miejsce mo\u017cemy przesun\u0105\u0107 s\u0105siaduj\u0105cy z nim klocek. Nazwijmy to ruchem podstawowym. Dlatego uk\u0142adanki tego typu nazywa si\u0119 r\u00f3wnie\u017c przesuwankami<\/em>. W pozycji z rysunku powy\u017cej mo\u017cemy jedynie wykona\u0107 dwa ruchy podstawowe, tj. w puste miejsce przesun\u0105\u0107 klocek 15 albo 12. Mo\u017cna r\u00f3wnie\u017c za jednym zamachem przesun\u0105\u0107 wi\u0119cej klock\u00f3w np. ca\u0142\u0105 kolumn\u0119, 4, 8, 12 w d\u00f3\u0142. Jest to jednak to samo co trzy ruchy podstawowe. Zatem wystarczy si\u0119 w naszych rozwa\u017caniach ograniczy\u0107 jedynie do ruch\u00f3w podstawowych. Nie mo\u017cemy wyjmowa\u0107 klock\u00f3w i w ten spos\u00f3b zamienia\u0107 ich miejscami. Zabawa polega na tym aby wykonuj\u0105c jedynie dozwolone ruchy, u\u0142o\u017cy\u0107 klocki w konkretny spos\u00f3b.<\/p>\n \nSwego czasu popularnym sta\u0142 si\u0119 problem nast\u0119puj\u0105cy. Jak z pozycji \\(P_0\\) otrzyma\u0107 poni\u017csz\u0105 (oznaczmy j\u0105 \\(Q\\))<\/p>\n powsta\u0142\u0105 przez zamian\u0119 miejscami klock\u00f3w o numerach 15 oraz 14.<\/p>\n \nProblem sta\u0142 si\u0119 na tyle popularny, \u017ce wspomniany Sam Loyd zaoferowa\u0142 za jego rozwi\u0105zanie a\u017c 1000 dolar\u00f3w. By\u0142o to ponad sto lat temu, wi\u0119c owa kwota by\u0142a warta wtedy wi\u0119cej ni\u017c obecne 1000 dolar\u00f3w. Nie by\u0142oby tej nagrody, gdyby nie to, \u017ce problem wydawa\u0142 si\u0119 niezwykle trudny, bo nikomu nie uda\u0142o si\u0119 znale\u017a\u0107 rozwi\u0105zania.<\/p>\n \nI nic dziwnego! Jak si\u0119 okazuje trudy ka\u017cdego \u015bmia\u0142ka by\u0142y daremne. Niemo\u017cliwe jest, wykonuj\u0105c tylko podstawowe przesuni\u0119cia klock\u00f3w, otrzymanie pozycji \\(Q\\) wychodz\u0105c od pozycji \\(P_0\\). Swoj\u0105 drog\u0105 je\u017celi z pewnej pozycji \\(P_1\\) da si\u0119, poprzez seri\u0119 ruch\u00f3w podstawowych, przej\u015b\u0107 do pozycji \\(P_2\\), to b\u0119dziemy m\u00f3wi\u0107, \u017ce \\(P_2\\) jest osi\u0105galna<\/em> z \\(P_1\\). To jak si\u0119 mogli czu\u0107 ci, kt\u00f3rym naprawd\u0119 zale\u017ca\u0142o na znalezieniu rozwi\u0105zania dobrze przedstawia poni\u017cszy rysunek z ksi\u0105\u017cki Sama Loyda Cyclopedia of Puzzles<\/em> na stronie 235.<\/p>\n \nCho\u0107 bardzo mo\u017cliwe, \u017ce Sam Loyd zaoferowa\u0142 tak sowit\u0105 nagrod\u0119 bo by\u0142 \u015bwiadom tego, \u017ce nikt nigdy nie b\u0119dzie w stanie tej nagrody wygra\u0107. Ca\u0142y za\u015b zabieg z nagrod\u0105 by\u0142 sprytnym chwytem marketingowym.<\/p>\n \nW tym wpisie najpierw poka\u017cemy, u\u017cywaj\u0105c prostego acz sprytnego argumentu, \u017ce istotnie nie da si\u0119 wspomnianego problemu rozwi\u0105za\u0107. Naturalnym uog\u00f3lnieniem, o kt\u00f3re a\u017c si\u0119 prosi, jest opis wszystkich pozycji, do kt\u00f3rych mo\u017cna doj\u015b\u0107 wychodz\u0105c od dowolnego u\u0142o\u017cenia \\(P\\). W drugiej cz\u0119\u015bci wpisu, wykorzystuj\u0105c jedynie podstawy algebry abstrakcyjnej, przedstawimy rozwi\u0105zanie og\u00f3lniejszego problemu. Wspomnimy r\u00f3wnie\u017c o dalszych uog\u00f3lnieniach. <\/p>\n \nKa\u017cdy ruch podstawowy sprowadza si\u0119 do zamiany pustego klocka z jego s\u0105siadem w poziomie lub w pionie. Gdyby plansza by\u0142a pomalowana w szachownic\u0119, to ka\u017cdy ruch podstawowy zmienia\u0142by kolor pola, na kt\u00f3rym znajduje si\u0119 pusty klocek. Wobec tego aby z pozycji \\(P_0\\) przej\u015b\u0107, poprzez seri\u0119 ruch\u00f3w podstawowych, do innej pozycji z pustym klockiem w tym samym miejscu, nale\u017cy wykona\u0107 parzyst\u0105 liczb\u0119 ruch\u00f3w. A pozycja \\(Q\\) ma pusty klocek w dok\u0142adnie tym samy miejscu co \\(P_0\\).<\/p>\n \nCi kt\u00f3rym nie obce jest poj\u0119cie parzysto\u015bci permutacji wiedz\u0105, \u017ce tyle wystarczy aby dowie\u015b\u0107, \u017ce takie przej\u015bcie, poprzez ruchy podstawowe, od \\(P_0\\) do \\(Q\\) jest niemo\u017cliwe. My jednak udowodnimy to tak aby i ci, kt\u00f3rzy tego poj\u0119cia nie znaj\u0105 byli zadowoleni.<\/p>\n \nW tym celu wprowadzimy poj\u0119cie nieporz\u0105dku. Ka\u017cda para klock\u00f3w maj\u0105cych numer (tzn. klocek pusty pomijamy!) gdzie ten o numerze wy\u017cszym znajduje si\u0119 wcze\u015bniej tworzy nieporz\u0105dek. Np. je\u017celi klocek o numerze 8 znajduje si\u0119 na polu wcze\u015bniejszym ni\u017c klocek o numerze 5, to para ta tworzy nieporz\u0105dek. Wymaga to wprowadzenia pewnej kolejno\u015bci p\u00f3l na planszy. Wybieramy t\u0119, kt\u00f3ra sama si\u0119 narzuca. <\/p>\n \nNa powy\u017cszym rysunku para klock\u00f3w 10 oraz 9 tworzy jeden z nieporz\u0105dk\u00f3w bo klocek 10 znajduje si\u0119 na polu wcze\u015bniejszym ni\u017c klocek 9. Dok\u0142adniej, klocek 10 jest na polui nr 1, za\u015b klocek 9 znajduje si\u0119 na polu nr 10. Z kolei pusty klocek znajduje si\u0119 na polu nr 11, a na polu nr 16 mamy klocek z liczb\u0105 11. <\/p>\n \nTeraz sprawdzimy w jaki spos\u00f3b ruchy podstawowe wp\u0142ywaj\u0105 na liczb\u0119 nieporz\u0105dk\u00f3w. Mamy dwa rodzaje ruch\u00f3w podstawowych: w poziomie oraz w pionie. Od razu zauwa\u017camy, \u017ce ka\u017cdy ruch w poziomie nie zmienia liczby nieporz\u0105dk\u00f3w.<\/p>\n \nInaczej sytuacja si\u0119 ma w przypadku ruch\u00f3w w pionie. W tym przypadku jeden z klock\u00f3w zmienia o 1 nr wiersza, w kt\u00f3rym si\u0119 znajduje. \u0141atwo zauwa\u017cy\u0107, \u017ce mi\u0119dzy miejscem klocka przed wykonaniem ruchu a jego miejscem po ruchu zawsze znajduj\u0105 si\u0119 trzy inne klocki, gdy m\u00f3wimy o ruchu w pionie. I to bez wzgl\u0119du na to, w kt\u00f3rej kolumnie ruch si\u0119 odbywa. Na rysunku ni\u017cej zaznaczone je ciemniejszym kolorem.<\/p>\n \nMamy na rysunku dwie przyk\u0142adowe sytuacje po wykonanym ruchu. Po lewej ruszono klockiem 5 w g\u00f3r\u0119, a po prawej klockiem 7 w d\u00f3\u0142. Je\u017celi ruszamy klockiem X w g\u00f3r\u0119, to spo\u015br\u00f3d stosownych trzech klock\u00f3w cz\u0119\u015b\u0107 (lub wszystkie) b\u0119d\u0105 mia\u0142y numery wi\u0119ksze od X, a cz\u0119\u015b\u0107 (lub wszystkie) numery mniejsze. Poniewa\u017c jest tych klock\u00f3w 3, to rozk\u0142ad numer\u00f3w tych klock\u00f3w na mniejsze-wi\u0119ksze mo\u017ce by\u0107 r\u00f3wny 3-0, 0-3, 2-1 lub 1-2.<\/p>\n \nPrzyjrzyjmy si\u0119 sytuacji z prawej strony. Przed wykonaniem ruchu klocki 8, 1, 9 znajdowa\u0142y si\u0119 za klockiem o numerze 7. Po wykonanym ruchu znajduj\u0105 si\u0119 przed nim. Poniewa\u017c 8 oraz 9 s\u0105 wi\u0119ksze ni\u017c 7, to otrzymali\u015bmy dwa nowe nieporz\u0105dki. Ponadto, klocek 1 znalaz\u0142 si\u0119 po ruchu przez klockiem 7. Zatem jeden nieporz\u0105dek nam uby\u0142. Teraz zauwa\u017cmy, \u017ce klocek 7 by\u0142 jedynym, kt\u00f3ry zmieni\u0142 swoje miejsce. St\u0105d je\u015bli para klock\u00f3w \\((a,b)\\), gdzie \\(a,b\\neq 7\\), by\u0142a nieporz\u0105dkiem, to pozostaje nim nadal. Podobnie je\u015bli nie by\u0142a, to nadal nie jest nieporz\u0105dkiem. Oznacza to, \u017ce liczba nieporz\u0105dk\u00f3w zmieni\u0142a si\u0119 o +2-1=+1.<\/p>\n \nAnalogicznie mo\u017cna pokaza\u0107, \u017ce bez wzgl\u0119du na rozk\u0142ad stosownych 3 klock\u00f3w na mniejsze-wi\u0119ksze, liczba nieporz\u0105dk\u00f3w zmieni si\u0119 o liczb\u0119 nieparzyst\u0105. Do tego, ka\u017cdy podstawowy ruch w pionie sprawia, \u017ce numer wiersza, w kt\u00f3rym znajduje si\u0119 puste pole zmienia si\u0119 o 1. Je\u017celi przez \\(N\\) oznaczymy liczb\u0119 nieporz\u0105dk\u00f3w, a przez \\(w\\) numer wiersza (licz\u0105c od g\u00f3rnego), w kt\u00f3rym znajduje si\u0119 puste pole, to przy ka\u017cdym pionowym ruchu \\(N+w\\) zmienia si\u0119 o liczb\u0119 parzyst\u0105. Tak samo jest w przypadku ruchu poziomego. Tu \\(N+w\\) si\u0119 nie zmienia. Teraz wystarczy zauwa\u017cy\u0107 jeszcze dwie rzeczy. W przypadku pozycji wyj\u015bciowej liczba nieporz\u0105dk\u00f3w jest r\u00f3wna 0, za\u015b puste pole znajduje si\u0119 w wierszu 4, tj. \\(N+w=4\\). Natomiast w przypadku pozycji z zamienionymi miejscami klockami 14 oraz 15 mamy jeden nieporz\u0105dek oraz puste pole w 4 wierszu, tj. \\(N+w=5\\). Jest to liczba nieparzysta, zatem nie da si\u0119 tej pozycji otrzyma\u0107 z pozycji wyj\u015bciowej wykonuj\u0105c jedynie legalne ruchy!!<\/p>\n \n \nWynik ten mimo i\u017c pokazuje, \u017ce problem z zamienionymi miejscami 14 oraz 15 nie jest rozwi\u0105zywalny, to jest zbyt osza\u0142amiaj\u0105cy. Nie pozwala na rozwi\u0105zanie narzucaj\u0105cego si\u0119 zagadnienia, kt\u00f3re pozycje mo\u017cna otrzyma\u0107 z pozycji wyj\u015bciowej wykonuj\u0105c jedynie ruchy podstawowe oraz czy maj\u0105c dan\u0105 pozycj\u0119 \\(P\\) mo\u017cna opisa\u0107 zbi\u00f3r wszystkich pozycji, kt\u00f3re mo\u017cna z niej otrzyma\u0107 wykonuj\u0105c jedynie legalne ruchy? Teraz zajmiemy si\u0119 tym zagadnieniem. Poni\u017csze rozumowanie pochodzi z (zacytowanej na ko\u0144cu) pracy Archera. <\/p>\n \nWprowad\u017amy teraz nieco inny porz\u0105dek p\u00f3l na planszy, na\u015bladuj\u0105cy w\u0119\u017cyka i przedstawiony poni\u017cej. Przyk\u0142adowo klocek o numerze 13 znajduje si\u0119 na polu 16. Za\u015b klocek pusty w polu o numerze 13. Ponadto, wprowad\u017amy poj\u0119cie rozmieszczenia<\/em>, kt\u00f3rym b\u0119dziemy nazywa\u0107 dowoln\u0105 bijekcj\u0119 ze zbioru klock\u00f3w (razem z pustym) do zbioru numer\u00f3w p\u00f3l na kwadratowej planszy.<\/p>\n \nWa\u017cn\u0105 obserwacj\u0105 jest to, \u017ce przesuwaj\u0105c pusty klocek wzd\u0142u\u017c w\u0119\u017cyka (tj. zgodnie z nowym porz\u0105dkiem), nie zmieniamy kolejno\u015bci niepustych klock\u00f3w, tj. tych maj\u0105cych numer. Wobec tego, mo\u017cemy okre\u015bli\u0107 relacj\u0119 r\u00f3wnowa\u017cno\u015bci, przyjmuj\u0105c rozmieszczenia za r\u00f3wnowa\u017cne, gdy jedno z drugiego mo\u017cemy otrzyma\u0107 przesuwaj\u0105c jedynie pusty klocek wzd\u0142u\u017c w\u0119\u017cyka. Klas\u0119 abstrakcji tej relacji nazywamy konfiguracj\u0105<\/em>. W ka\u017cdym rozmieszczeniu z danej, konkretnej konfiguracji, kolejno\u015b\u0107 niepustych klock\u00f3w jest taka sama. Za\u015b numery p\u00f3l, kt\u00f3re klocki zajmuj\u0105 w danej konfiguracji nazywamy slotami<\/em>. Je\u017celi klocek zajmuje np. pole 5 na planszy oraz puste miejsce jest za nim, to klocek ten ma slot nr 5. Je\u015bli natomiast klocek pi\u0105ty znajduje si\u0119 w polu np. 3, to klocek ma slot 4.<\/p>\n \n \nNa rysunku klocek 9 znajduje si\u0119 w polu o numerze 15, ale poniewa\u017c pusty klocek znajduje si\u0119 przed polem 15, to klocek 9 jest w slocie 14. \nKa\u017cdy ruch podstawowy wp\u0142ywa (lub nie) na u\u0142o\u017cenie slot\u00f3w w konfiguracji, tzn. prowadzi do pewnej ich permutacji. Oznaczmy przez \\(\\sigma_{i,j}\\) permutacj\u0119 slot\u00f3w, do kt\u00f3rej prowadzi przesuni\u0119cie pustego klocka z \\(i\\)-tego pola na planszy do pola \\(j\\). Poniewa\u017c przesuwaj\u0105c pusty klocek wzd\u0142u\u017c w\u0119\u017cyka nie zmieniamy kolejno\u015bci slot\u00f3w, to permutacja \\(\\sigma_{i,i+1}\\) jest identyczno\u015bci\u0105 na slotach. Ponadto, \\(\\sigma_{i,j}=\\sigma_{j,i}^{-1}\\).<\/p>\n \nW tym miejscu uwidacznia si\u0119 pewna zaleta przyj\u0119cia w\u0119\u017cykowego porz\u0105dku p\u00f3l na planszy. Dzi\u0119ki temu do rozwa\u017cenia s\u0105 jedynie ruchy prowadz\u0105ce do nietrywialnych permutacji \\[\\sigma_{1,8}, \\sigma_{2,7}, \\sigma_{3,6}, \\sigma_{5,12}, \\sigma_{6,11}, \\sigma_{7,10}, \\sigma_{9,16}, \\sigma_{10,15}, \\sigma_{11,14}.\\] Dla przyk\u0142adu zobaczmy jak\u0105 permutacj\u0105 jest \\(\\sigma_{1,8}\\), tzn. ta powodowana przez przesuni\u0119cie pustego klocka z pola 1 do pola 8.<\/p>\n \nPrzed takim ruchem, pusty klocek znajduje si\u0119 w polu 1, tj. pierwszy slot znajduje si\u0119 w polu 2. Wykonawszy wspomniany ruch, sprawiamy, \u017ce wszystkie sloty od 1 do 6 zwi\u0119kszaj\u0105 sw\u00f3j numer o 1 bo w polu nr 1 pojawi\u0142 si\u0119 niepusty klocek. A poniewa\u017c klocek ten przed ruchem znajdowa\u0142 si\u0119 w si\u00f3dmym z kolei niepustym polu, to po ruchu znajduje si\u0119 w slocie o numerze 1. Natomiast sloty o numerach wi\u0119kszych ni\u017c 7 pozostaj\u0105 bez zmian. Ostatecznie \\[\\sigma_{1,8}=(1,2,3,4,5,6,7).\\] W analogiczny spos\u00f3b mo\u017cna zauwa\u017cy\u0107, \u017ce \nTeraz poka\u017cemy, \u017ce zbi\u00f3r \\(A\\) wy\u017cej wymienionych permutacji oraz ich odwrotno\u015bci generuje grup\u0119 alternuj\u0105c\u0105 \\(A_{15}\\). St\u0105d od razu wynika, \u017ce prawdziwe jest nast\u0119puj\u0105ce twierdzenie:<\/p>\n Twierdzenie 1<\/strong> \nMo\u017cemy je r\u00f3wnie\u017c sformu\u0142owa\u0107 w j\u0119zyku rozmieszcze\u0144. Je\u017celi rozmieszczenia \\(P_1\\) oraz \\(P_2\\) maj\u0105 pusty klocek w tym samym polu, to \\(P_2\\) jest osi\u0105galne z \\(P_1\\) wtedy i tylko wtedy, gdy \\(P_2\\) jest parzyst\u0105 permutacj\u0105 \\(P_1\\). Ka\u017cdy ruch podstawowy jest pewn\u0105 transpozycj\u0105. Wobec tego je\u017celi \\(P_1\\) oraz \\(P_2\\) maj\u0105 pusty klocek w r\u00f3\u017cnych polach, to mo\u017cemy w og\u00f3lno\u015bci sformu\u0142owa\u0107 nast\u0119puj\u0105ce twierdzenie:<\/p>\n \nNiech rozmieszczenie \\(P_1\\) ma pusty klocek w polu o numerze \\(a_1\\) za\u015b \\(P_2\\) w polu \\(a_2\\) oraz niech \\(n\\) b\u0119dzie liczb\u0105 ruch\u00f3w podstawowych jak\u0105 nale\u017cy wykona\u0107 aby przej\u015b\u0107 od pola \\(a_1\\) do pola \\(a_2\\). W\u00f3wczas rozmieszczenie \\(P_2\\) jest osi\u0105galne z \\(P_1\\) wtedy i tylko wtedy, gdy \\(P_2\\) jest permutacj\u0105 \\(P_1\\) tej samej parzysto\u015bci co liczba \\(n\\).\n<\/p><\/blockquote>\n \nRozmieszczenia \\(P_0\\) oraz \\(Q\\) maj\u0105 pusty klocek w tym samym polu, tj. \\(n=0\\) w tym przypadku. Wi\u0119c \\(Q\\) si\u0119 nie da, jak ju\u017c wiemy, otrzyma\u0107 z \\(P_0\\) bo \\(Q\\) jest nieparzyst\u0105 permutacj\u0105 \\(P_0\\). Ale przejd\u017amy do dowodu.<\/p>\n \nZacznijmy od przytoczenia (bez dowodu) znanego, standardowego lematu<\/p>\n Lemat 1<\/strong> \nOkazuje si\u0119, \u017ce mo\u017cna zbi\u00f3r wszystkich 3-cykli zredukowa\u0107.<\/p>\n Lemat 2<\/strong> \nDow\u00f3d:<\/i> \nTeraz mo\u017cemy udowodni\u0107 nast\u0119puj\u0105ce twierdzenie:<\/p>\n \nTwierdzenie<\/strong> \nDow\u00f3d:<\/i> \nZ powy\u017cszego twierdzenia wynika w szczeg\u00f3lno\u015bci, \u017ce relacja r\u00f3wnowa\u017cno\u015bci \\(\\sim\\), gdzie \\(P_1\\sim P_2\\) o ile, rozmieszczenie \\(P_1\\) mo\u017cna otrzyma\u0107 z \\(P_2\\) poprzez seri\u0119 ruch\u00f3w podstawowych (i vice versa<\/em>) ma dwie klasy abstrakcji. <\/p>\n \nNaturalnym pytaniem jest to jak si\u0119 sprawy maj\u0105 w przypadku w przypadku plansz o innych wymiarach czy nawet innych kszta\u0142tach. Czy Twierdzenie 1 pozosta\u0142oby prawdziwe gdyby plansza mia\u0142a inne wymiary ni\u017c 4×4? Czy mo\u017ce w takiej sytuacji relacja \\(\\sim\\) mia\u0142aby inn\u0105 liczb\u0119 klas abstrakcji? Om\u00f3wimy teraz, z grubsza, sytuacj\u0119 znacznie og\u00f3lniejsz\u0105.<\/p>\n \nCa\u0142a zabawa w pi\u0119tnastk\u0119 polega w zasadzie na przemieszczaniu pustego klocka w pole z nim s\u0105siaduj\u0105ce. Prowadzi to do pomys\u0142u aby rozwa\u017ca\u0107 takie przesuwanie nie po prostok\u0105tnej planszy lecz mi\u0119dzy wierzcho\u0142kami grafu. Ka\u017cdy wierzcho\u0142ek to pole. Klocki mo\u017cemy przesuwa\u0107 jedynie mi\u0119dzy polami s\u0105siednimi czyli po\u0142\u0105czonymi kraw\u0119dzi\u0105. Pomys\u0142 ten by\u0142 rozwa\u017cany w, cytowanej na ko\u0144cu, pracy Wilsona.<\/p>\n \nPrzyk\u0142adowo, je\u017celi pola na planszy do pi\u0119tnastki uznamy za wierzcho\u0142ki grafu, kt\u00f3re s\u0105 po\u0142\u0105czone kraw\u0119dzi\u0105, gdy ze sob\u0105 s\u0105siaduj\u0105, to graf ten b\u0119dzie wygl\u0105da\u0142 nast\u0119puj\u0105co: \nCo oczywiste, ograniczymy si\u0119 jedynie do graf\u00f3w sp\u00f3jnych. Mo\u017ce si\u0119 wydawa\u0107, \u017ce w przypadku graf\u00f3w, twierdzenie analogiczne do Twierdzenia 1 jest trudne do sformu\u0142owania w tak zgrabny i przyst\u0119pny spos\u00f3b. Okazuje si\u0119 jednak, \u017ce w takiej znacznie og\u00f3lniejszej sytuacji, opis klas abstrakcji relacji \\(\\sim\\) jest nadzwyczaj prosty. <\/p>\n \nIde\u0119, kt\u00f3r\u0105 zastosowali\u015bmy do klasycznej pi\u0119tnastki, mo\u017cna z powodzeniem zastosowa\u0107 do plansz b\u0119d\u0105cych grafami maj\u0105cymi drog\u0119 Hamiltona, tj. przechodz\u0105c\u0105 przez wszystkie wierzcho\u0142ki tylko raz. Porz\u0105dek w\u0119\u017cykowy jaki przyj\u0119li\u015bmy na planszy do pi\u0119tnastki jest przyk\u0142adem takiej drogi. Przechodzi ona przez wszystkie pola (wierzcho\u0142ki) tylko raz. Gdyby\u015bmy zamiast w\u0119\u017cykowego, przyj\u0119li porz\u0105dek spiralny, to w r\u00f3wnie\u017c da\u0142oby si\u0119 udowodni\u0107 Twierdzenie 1.<\/p>\n \nSp\u00f3jrzmy na inny graf. Dobrym przyk\u0142adem jest s\u0142ynny graf Petersena. Jest to graf maj\u0105cy drog\u0119 Hamiltona.<\/p>\n \nMo\u017cna pokaza\u0107, \u017ce permutacje \\[\\sigma_{1,9}, \\sigma_{1,5}, \\sigma_{2,7}, \\sigma_{3,10},\\sigma_{4,8}\\textrm{ oraz } \\sigma_{6,10}\\] generuj\u0105 ca\u0142e \\(S_9\\). W tym przypadku ka\u017cde rozmieszczenie mo\u017cna otrzyma\u0107 z ka\u017cdego.<\/p>\n \nZupe\u0142nie inaczej sytuacja wygl\u0105da z grafami cyklicznymi. W ich przypadku \u017caden ruch podstawowy nie zmienia konfiguracji niepustych klock\u00f3w!<\/p>\n \nW dalszej cz\u0119\u015bci rozwa\u017ca\u0107 b\u0119dziemy grafy proste – tj. bez kraw\u0119dzi wielokrotnych oraz bez p\u0119tli. Do tego zak\u0142adamy, \u017ce graf jest dwusp\u00f3jny czyli nie zawiera wierzcho\u0142k\u00f3w, kt\u00f3re go rozspajaj\u0105. W takiej sytuacji nie da si\u0119 \u017cadnego niepustego klocka przesun\u0105\u0107 przez taki wierzcho\u0142ek i problem rozpada si\u0119 do analogicznego zagadnienia w ka\u017cdej sk\u0142adowej sp\u00f3jno\u015bci powsta\u0142ej po usuni\u0119ciu takiego wierzcho\u0142ka.<\/p>\n \nDla grafu \\(G\\) mo\u017cemy, analogicznie jak w przypadku pi\u0119tnastki, wprowadzi\u0107 poj\u0119cie rozmieszczenia. Polami b\u0119d\u0105 wierzcho\u0142ki grafu. Oznaczmy przez \\(p(G)\\) zbi\u00f3r wszystkich rozmieszcze\u0144. Zbi\u00f3r \\(p(G)\\) mo\u017cemy uto\u017csamia\u0107 z wierzcho\u0142kami nowego grafu, kt\u00f3re s\u0105 po\u0142\u0105czone kraw\u0119dzi\u0105 tylko gdy rozmieszczenie \\(P_2\\) mo\u017cna otrzyma\u0107 z \\(P_1\\) poprzez ruch podstawowy.<\/p>\n \nW takiej interpretacji, problem czy rozmieszczenie \\(P_2\\) jest osi\u0105galne z \\(P_1\\) sprowadza si\u0119 do tego tego czy \\(P_1\\) oraz \\(P_2\\) le\u017c\u0105 w tej samej sk\u0142adowej sp\u00f3jno\u015bci grafu \\(p(G)\\). Okazuje si\u0119, \u017ce prawdziwe jest nast\u0119puj\u0105ce twierdzenie:<\/p>\n \nTwierdzenie (Wilson)<\/strong> \nGraf \\(G\\) odpowiadaj\u0105cy planszy do klasycznej pi\u0119tnastki jest grafem dwudzielnym, wi\u0119c \\(p(G)\\) ma dwie sk\u0142adowe sp\u00f3jno\u015bci (co ju\u017c wiemy). <\/p>\n \nA.F. Archer<\/strong>, A Modern Treatment of the 15 Puzzle<\/em>, Amer. Math. Monthly 106 (1999), s. 793-799 Pi\u0119tnastka jest uk\u0142adank\u0105 o bardzo prostych regu\u0142ach. Trzeba przesuwa\u0107 klocki w taki spos\u00f3b, aby otrzyma\u0107 po\u017c\u0105dan\u0105 pozycj\u0119. Mimo swej prostoty jest \u017ar\u00f3d\u0142em ciekawych problem\u00f3w, kt\u00f3re mo\u017cna rozwi\u0105za\u0107 przy pomocy matematyki.<\/p>\n","protected":false},"author":1,"featured_media":1592,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[64,56,49,47],"tags":[66,65,67,50,48],"yoast_head":"\n![\"pi\u0119tnastka\"](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15a_03.png\")
<\/p>\n![\"pi\u0119tnastka\"](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15a_04.jpg\")
<\/p>\n![\"gra](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15c_05.png\")
<\/p>\n![\"uk\u0142adanka](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15a_06.png\")
![\"pi\u0119tnastka\"](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15a_07.png\")
<\/p>\n![\"pi\u0119tnastka\"](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15_02.png\")
<\/p>\n![\"15](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15_08.png\")
<\/p>\n
\nOg\u00f3lnie, powy\u017csze rozmieszczenie odpowiada konfiguracji \\([1,2,3,4,8,7,6,5,14,12,13,10,15,11,9]\\).<\/p>\n
\n\\[\\begin{array}{lll}\\sigma_{2,7} & = & (2,3,4,5,6)\\\\ \\sigma_{3,6} & = & (3,4,5)\\\\ \\sigma_{5,12} & = & (5,6,7,8,9,10,11)\\\\ \\sigma_{6,11} & = & (6,7,8,9,10)\\\\ \\sigma_{7,10} & = & (7,8,9)\\\\ \\sigma_{9,16} & = & (9,10,11,12,13,14,15)\\\\ \\sigma_{10,15} & = & (10,11,12,13,14)\\\\ \\sigma_{11,14} & = & (11,12,13) \\end{array}\\]<\/p>\n\n
\nNiech \\(P_1\\) oraz \\(P_2\\) b\u0119d\u0105 rozmieszczeniami nale\u017c\u0105cymi odpowiednio do konfiguracji \\(K_1\\) oraz \\(K_2\\). W\u00f3wczas \\(P_2\\) mo\u017cna otrzyma\u0107 z \\(P_1\\) poprzez seri\u0119 ruch\u00f3w podstawowych wtedy i tylko wtedy, gdy \\(K_2\\) jest parzyst\u0105 permutacj\u0105 \\(K_1\\).\n<\/p><\/blockquote>\n\n
\n
\nJe\u017celi \\(n\\geqslant 3\\), to cykle d\u0142ugo\u015bci 3 generuj\u0105 \\(A_n\\).\n<\/p><\/blockquote>\n\n
\nJe\u017celi \\(n\\geqslant 3\\), to cykle \\(X_n=\\{(1,2,3), (2,3,4),\\ldots, (n-2, n-1,n)\\}\\) generuj\u0105 \\(A_n\\).\n<\/p><\/blockquote>\n
\nNa mocy lematu 1, wystarczy pokaza\u0107, \u017ce \\(X_n\\) generuje wszystkie 3-cykle.
\nPoniewa\u017c \\(A_3=\\{\\textrm{id},(1,2,3),(1,3,2)\\}\\) jest generowana przez \\((1,2,3)\\), to dla \\(n=3\\) lemat jest prawdziwy. Za\u0142\u00f3\u017cmy, \u017ce jest prawdziwy dla pewnego \\(n\\geqslant 3\\). Zauwa\u017cmy, \u017ce w\u0142o\u017cenie \\[\\{1,2,3,\\ldots,n\\}\\to \\{1,2,3,\\ldots,n,n+1\\}\\] prowadzi do w\u0142o\u017cenia \\[\\alpha: A_n\\to A_{n+1},\\] gdzie \\(\\alpha(\\sigma)(i)=\\sigma(i)\\) dla \\(i\\neq n+1\\) oraz \\(\\alpha(\\sigma)(n+1)=n+1\\). St\u0105d wynika, \u017ce \\(\\alpha(X_n)\\), a wi\u0119c w szczeg\u00f3lno\u015bci \\(X_{n+1}\\) generuje 3-cykle niezawieraj\u0105ce n+1.
\nAnalogicznie, funkcja \\[\\{1,2,3,\\ldots,n\\}\\to \\{1,2,3,\\ldots,n,n+1\\},\\ i\\mapsto i+1\\] prowadzi do w\u0142o\u017cenia \\[\\beta: A_n\\to A_{n+1},\\] gdzie \\(\\beta(\\sigma)(i)=\\sigma(i+1)\\) dla \\(i\\neq 1\\) oraz \\(\\beta(\\sigma)(1)=1\\). St\u0105d wynika, \u017ce \\(X_{n+1}\\) generuje wszystkie 3-cykle niezawieraj\u0105ce jednocze\u015bnie 1 oraz n+1. Na koniec wystarczy zauwa\u017cy\u0107, \u017ce dla \\(y\\in \\{1,2,\\ldots, n+1\\}\\setminus \\{1,x,n+1\\}\\) zachodzi \\[(1,x,n+1)=(y,x,n+1)(1,x,y)\\] oraz \\[(1,n+1,x)=(1,x,n+1)(1,x,n+1).\\]<\/p>\n\n
\nZbi\u00f3r \\(A\\) wymienionych wcze\u015bniej permutacji generuje \\(A_{15}\\).\n<\/p><\/blockquote>\n
\nPoniewa\u017c wszystkie permutacje z \\(A\\) s\u0105 parzyste, to \\(A\\) generuje pewn\u0105 podgrup\u0119 \\(A_{15}\\). Poka\u017cemy, \u017ce generuje on wszystkie permutacje z \\(X_{15}\\), tym samym dowodz\u0105c, na mocy lematu 2, \u017ce zbi\u00f3r \\(A\\) generuje \\(A_{15}\\). Istotnie, zauwa\u017cmy na pocz\u0105tek, \u017ce dla dowolnej permutacji \\(\\sigma\\) zachodzi \\[\\sigma (a_1,a_2,\\ldots,a_n)\\sigma^{-1}=(a_1\\sigma, a_2\\sigma,\\ldots,a_n\\sigma).\\] Podstawiaj\u0105c kolejno \\(n=-2,-1,0,1,2\\), z\u0142o\u017cenia \\[\\sigma_{1,8}^{-n}\\sigma_{3,6}\\sigma_{1,8}^n\\] prowadz\u0105 do cykli \\((1,2,3),\\ldots,(5,6,7)\\). Podobnie, \\[\\sigma_{5,12}^{-n}\\sigma_{7,10}\\sigma_{5,12}^n\\] prowadz\u0105 do \\((5,6,7),\\ldots, (9,10,11)\\). Za\u015b z\u0142o\u017cenia \\[\\sigma_{9,16}^{-n}\\sigma_{11,14}\\sigma_{9,16}^n\\] daj\u0105 cykle \\((9,10,11),\\ldots,(13,14,15)\\). Otrzymali\u015bmy wi\u0119c wszystkie cykle z \\(X_{15}\\) co ko\u0144czy dow\u00f3d.<\/p>\n![\"pi\u0119tnastka\"](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15_04.png\")
<\/p>\n![\"graf](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15_05.png\")
<\/p>\n\n
\nJe\u017celi \\(G\\) jest prostym grafem dwusp\u00f3jnym nieb\u0119d\u0105cym ani grafem cyklicznym ani grafem dwudzielnym ani poni\u017cszym grafem \\(\\theta\\) ![\"pi\u0119tnastka\"](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2022\/06\/15_07.png\")
to graf \\(p(G)\\) jest sp\u00f3jny. Je\u017celi \\(G\\) jest grafem dwudzielnym, to \\(p(G)\\) ma dwie sk\u0142adowe sp\u00f3jno\u015bci, za\u015b \\(p(\\theta)\\) ma sze\u015b\u0107 sk\u0142adowych sp\u00f3jno\u015bci.\n<\/p><\/blockquote>\nLiteratura<\/h4>\n
\nR.M. Wilson<\/strong>, Graph Puzzles, Homotopy and the Alternating Group<\/em>, J. Combin. Theory Ser. B 16 (1974), s. 86-96<\/p>\n","protected":false},"excerpt":{"rendered":"