Piętnastka (układanka)

Zobacz multimedia związane z tematem: Piętnastka (układanka)

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].

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.

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 ${\displaystyle P}$ oraz ${\displaystyle Q}$ mają puste pole w tym samym miejscu, to ułożenie ${\displaystyle Q}$ można otrzymać z ułożenia ${\displaystyle P}$ wtedy i tylko wtedy, ${\displaystyle Q}$ jest parzystą permutacją ${\displaystyle P}$^[4].

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 ${\displaystyle G}$ jest prostym, grafem 2-spójnym, który nie jest ani grafem cyklicznym ani grafem dwudzielnym oraz jest różny od grafu ${\displaystyle \theta _{0},}$ to każde ułożenie jest osiągalne z każdego innego^[6].

• klotski

• Eric W.E.W. Weisstein Eric W.E.W., 15 Puzzle, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
• Układanka piętnastka i ukryta w niej matematyka, blog beta-iks.pl, 13 października 2022 [dostęp 2022-11-28] (pl.).