MAT-ŚWIAT › Szalone liczby

Piętnastka - rozgrzewka

Data ostatniej modyfikacji:
2014-01-16
Autor: 
Krzysztof Omiljanowski
pracownik IM UWr
Poziom edukacyjny: 
szkoła podstawowa
gimnazjum
szkoła średnia z maturą
szkoła profilowana zawodowa
Dział matematyki: 
łamigłówki logiczne
matematyka rozrywkowa
kombinatoryka
teoria grafów

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ę G0 (o n0 = 7 polach).
 

 

G0

licznik: 0    

Jest tutaj p0 = 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 d0 = 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 G1, G2,..., G26 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.

 

 

G1

licznik: 0    
G2

licznik: 0    
G3

licznik: 0    

 

 

G4

licznik: 0    
G5

licznik: 0    
G6

licznik: 0    

 

 

G7

licznik: 0    
G8

licznik: 0    
G9

licznik: 0    

 

 

G10

licznik: 0    
G11

licznik: 0    
G12

licznik: 0    
G13

licznik: 0    

 

 

G14

licznik: 0    
G15

licznik: 0    
G16

licznik: 0    

 

 

G17

licznik: 0    
G18

licznik: 0    
G19

licznik: 0    

 

 

G20

licznik: 0    
G21

licznik: 0    

 

 

G22

licznik: 0    

 

 

G23

licznik: 0    
G24

licznik: 0    

 

 

G25*

licznik: 0    
G26**

licznik: 0    

 

Zagadki

Kamil (niezweryfikowany), wtorek, 17/11/2015 - 22:23

Podobają mi się wasze zagadki, trzeba trochę pogłówkować

Powrót na górę strony