Przejdź do zawartości

Piętnastka (układanka)

Z Wikipedii, wolnej encyklopedii
Początkowy układ, który pojawił się w zagadce
Końcowy poprawny układ w „piętnastce”, jaki miał zostać osiągnięty
Piętnastka użyta jako satyra polityczna

Piętnastka, taquin (z fr.), pot. „przesuwanka” – układanka zbudowana z pudełka, w którym znajduje się 15 kwadratowych klocków o jednakowych rozmiarach ułożonych w kwadrat 4×4 i ponumerowanych od 1 do 15. Jedno miejsce jest puste i umożliwia przesuwanie sąsiednich klocków względem siebie. Uważana jest za pierwowzór kostki Rubika[1].

Cel gry

[edytuj | edytuj kod]

Celem gry jest ułożenie klocków w określony sposób, najczęściej w porządku rosnącym od 1 do 15 bądź innym określonym warunkami zadania, przez przesuwanie ich względem siebie w pudełku. Możliwe są również inne układy, jak również zastąpienie liczb rysunkiem lub hasłem słownym. Zamiana klocków miejscami jest niedozwolona.

Historia

[edytuj | edytuj kod]

Początki układanki są nieznane. W 1878 roku amerykański specjalista zajmujący się grami Samuel Loyd rozpropagował układankę, choć najpewniej nie był to jego własny pomysł, a gra była znana wcześniej[2]. Pierwszym zadaniem z użyciem układanki było doprowadzenie z układu dolnego rzędu 13 – 15 – 14 do układu rosnącego. Za rozwiązanie wyznaczono nagrodę 1000 dolarów. Wybuchła prawdziwa gorączka, lecz nikt nie znalazł prawidłowego rozwiązania[2], bo jest to niemożliwe[3].

Łatwo to pokazać. Gdyby pola w pudełku były pokolorowane w szachownicę, to każdy ruch sprawiałby, że miejsce puste znalazłoby się w polu o innym kolorze niż przed ruchem. Czyli aby z ułożenia, w którym klocki są ułożone rosnąco dojść do jakiegokolwiek innego ułożenia mającego puste miejsce w dolnym prawym rogu należy wykonać parzystą liczbę ruchów. Zatem każde ułożenie jakie można otrzymać wychodząc od ułożenia klocków w porządku rosnącym jest permutacją parzystą takiego ułożenia. Natomiast ułożenie, w którym jedynie klocki 14 oraz 15 zostały zamienione miejscami, a inne pozostają na swoich pierwotnych miejscach jest permutacją nieparzystą ułożenia rosnącego (dokładniej jest jej transpozycją) oraz ma puste miejsce w tym samym polu[4][5].

Można pokazać nawet więcej. Jeżeli ułożenia oraz mają puste pole w tym samym miejscu, to ułożenie można otrzymać z ułożenia wtedy i tylko wtedy, jest parzystą permutacją [4].

Uogólnienia

[edytuj | edytuj kod]

Naturalnym problemem wydaje się rozważanie tego, które ułożenia można otrzymać z których na planszach o innych wymiarach niż 4x4 czy nawet o innych kształtach. W ogólności, można przesuwać klocki między sąsiednimi wierzchołkami grafu spójnego. Okazuje się w takiej sytuacji, że jeżeli jest prostym, grafem 2-spójnym, który nie jest ani grafem cyklicznym ani grafem dwudzielnym oraz jest różny od grafu to każde ułożenie jest osiągalne z każdego innego[6].

Graf

Zobacz też

[edytuj | edytuj kod]

Przypisy

[edytuj | edytuj kod]
  1. Trochę teorii. [dostęp 2011-10-27]. [zarchiwizowane z tego adresu (2017-03-20)].
  2. a b The history of the 15 puzzle.. [dostęp 2011-10-13]. (ang.).
  3. Hugo Steinhaus: Kalejdoskop matematyczny. Wyd. IV. Warszawa: WSP, 1989, s. 21–23. ISBN 83-02-02326-4.
  4. a b A.F. Archer: A Modern Treatment of the 15 Puzzle, Amer. Math. Monthly 106 (1999), s. 793–799.
  5. W.W. Johnson: Notes on the „15” Puzzle, American Journal of Mathematics 2 (1879), s. 397–404.
  6. R.M. Wilson: Graph Puzzles, Homotopy and the Alternating Group, J. Combin. Theory Ser. B 16 (1974), s. 86–96.

Linki zewnętrzne

[edytuj | edytuj kod]