thumb|Początkowy układ, który pojawił się w zagadce thumb|Końcowy poprawny układ w „piętnastce”, jaki miał zostać osiągnięty thumb|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.
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 poluA.F. Archer: A Modern Treatment of the 15 Puzzle, Amer. Math. Monthly 106 (1999), s. 793–799.W.W. Johnson: Notes on the „15” Puzzle, American Journal of Mathematics 2 (1879), s. 397–404..
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ą .
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 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 innegoR.M. Wilson: Graph Puzzles, Homotopy and the Alternating Group, J. Combin. Theory Ser. B 16 (1974), s. 86–96.. thumb|Graf
Zobacz też klotski
Przypisy
Linki zewnętrzne
Układanka piętnastka i ukryta w niej matematyka, blog beta-iks.pl, 13 października 2022 [dostęp 2022-11-28] (pl.).
Kategoria:Układanki