Piętnastka (układanka)

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

Szablon:Commonscat 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.

Cel gry

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

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. 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, bo jest to niemożliwe.

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

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

Uogólnienia

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

Graf ${\theta }_0$

Zobacz też

• klotski

Linki zewnętrzne

• Szablon:MathWorld
• Układanka piętnastka i ukryta w niej matematyka, blog beta-iks.pl, 13 października 2022 [dostęp 2022-11-28] (pl.).