Piętnastka - rozgrzewka

więcej informacji o tekście:

Krzysztof Omiljanowski

Piętnastka jest popularną łamigłówką znaną od ponad stu lat (piszemy o niej na Portalu tutaj). Dziś znany jest także algorytm jej układania, co z jednej strony może popsuć całą zabawę, a z drugiej - pokazuje matematyczną złożoność tej niepozornej zabawki. Proponujemy zbadanie kilkunastu prostszych wersji gry w piętnastkę. Dzięki temu można będzie lepiej zrozumieć bogactwo wersji oryginalnej.

Gra w piętnastkę polega na przesuwaniu pól planszy tak, by dojść do celu (pozycja reset).
W jednym ruchu można przesunąć na puste pole któreś z pól sąsiadujących z nim bokiem (kliknij).

licznik: 0

Po potasowaniu pól na planszy z danej pozycji można dojść do celu na wiele sposobów. Najmniejszą liczbę ruchów potrzebnych do osiągnięcia celu nazwiemy odległością danej pozycji od celu.
Wiadomo, że na tej planszy (o n = 16 polach) jest p = 16! / 2 = 10461394944000 pozycji, z których można dojść do celu i d = 80 jest odległością od celu najdalszej z nich. Ale nie jest to wcale łatwe do uzasadnienia.

Rozpatrzymy tu radykalnie prostsze wersje tej łamigłówki. Zmieniać się będą plansze i liczba pól n. Reguły przesuwania pozostają te same.

Na początek rozpatrzmy poniższą planszę G₀ (o n₀ = 7 polach).

G₀

licznik: 0

Jest tutaj p₀ = 21 wszystkich możliwych pozycji (łącznie z celem), z których można dojść do celu:

        - cel,             - w odległości 1 od celu,

     - w odległości 2 od celu,      - w odległości 3 od celu,

        - w odległości 4 od celu,

        - w odległości 5 od celu,

        - w odległości 6 od celu,

        - w odległości 7 od celu,

        - w odległości 8 od celu.

Są zatem 4 pozycje o największej odległości d₀ = 8 od celu.

Proponujemy samodzielne zbadanie poniższych łamigłówek. Początkowe przykłady są bardzo proste.

Zadanie. Dla każdej z poniższych łamigłówek G₁, G₂,..., G₂₆ podaj:
a) liczbę p wszystkich pozycji, z których można dojść do celu,
b) liczbę d będącą największą z odległości pozycji od celu,
c*) przykład pozycji w odległości d od celu.