Wyskakać do jednego, czyli o zmaganiach z samotnikiem
Bicie przeskokiem jest typowe dla wielu gier; najbardziej znaną z nich są warcaby. Podstawowy wariant takiego bicia występuje, gdy dwa pionki stoją na sąsiednich polach i tuż za jednym z nich jest wolne pole – wówczas drugim można przez pierwszy na to pole przeskoczyć, a następnie przeskoczony pionek usunąć (rys. 1). Wprawdzie w warcabach bicia wykonuje się na ukos i sąsiednimi są pola stykające się tylko rogiem, jednak na jasnych polach nie ma gry, więc w tym przypadku szachownica jest izomorficzna z planszą złożoną z 32 kwadratowych pól (rys. 2a), na której pionki biją jak na rys. 1.
Jeśli taką planszę obrócimy o 45 stopni w prawo (rys. 2b) i nieco zmodyfikujemy, usuwając dwa wystające pola i dodając w środku pionowy rząd pól – to powstanie plansza łamigłówki wielochodowej (rys. 2c), czyli gry dla jednej osoby, zwanej samotnikiem (solitaire), która debiutowała na przełomie XVII i XVIII wieku na dworze Króla Słońce, Ludwika XIV. Warcabowy rodowód tej łamigłówki jest bardzo prawdopodobny, ale pewności nie ma, bo w zachowanych materiałach źródłowych z końca XVII wieku brak informacji o genezie zabawy, zaś ówczesna ikonografia (dwie grawiury, przedstawiające damy przy planszy) świadczy tylko o jej dużej popularności.
Reguły były bardzo proste: na wszystkich 37 polach umieszczano pionki, po czym jeden dowolny usuwano i zaczynano serię warcabowych skoków-bić. Chodziło o to, aby w momencie, gdy kontynuowanie „wybitki” dobiegło końca, a więc nigdzie nie występował układ taki, jak na rys. 1 u góry, na planszy pozostało jak najmniej pionków – im mniej, tym lepszy wynik, czyli wyższa wygrana z samym sobą.
W drugiej połowie XVIII wieku samotnik był już znany w całej Europie, a plansza z rys. 2c została nieco zmieniona – przybrała kształt krzyża po usunięciu czterech pól (rys. 3) i taka jest dziś najpopularniejsza. Zaostrzono także regułę dotyczącą końcówki – wygraną stanowi „wybitka” zakończona pozostawieniem tylko jednego pionka. Później, zwłaszcza w XX wieku, pojawiały się samotniki z planszami różnego kształtu i wielkości.
Klasyczny samotnik zaliczany jest wprawdzie do zabaw logicznych, ale praktycznie logika zaczyna się, gdy na planszy pozostaje nie więcej niż 10–12 pionków. Wcześniej rozgrywka jest skakaniem na chybił-trafił (chyba że korzysta się z „gotowców”), zwłaszcza że do celu wiedzie wiele różnych dróg. Dlatego logicznie ciekawsze są mniejsze samotnikowe układy na prostokątnych planszach, z których nie usuwa się na początku pionka, bo otaczające układ wolne pola od razu umożliwiają wykonywanie skoków. Takie układy mogą być łatwe do rozwiązania, jak np. trzy na rys. 4 (przykładowe rozwiązanie pierwszego oznaczono), trudne – rys. 5 lub… nierozwiązywalne – rys. 6; dowód, że utworzonego z 9 pionków kwadratu nie sposób wyskakać do jednego pionka będzie podany dalej, ale warto spróbować znaleźć go samemu.
Wstęp do matematyki samotnika zaczniemy od jego wersji najprostszej – jednowymiarowej. Plansza jest rzędem n pól; na wszystkich stoją pionki. Przeskoki poprzedza usunięcie jednego z nich. Który wybrać, by możliwe było wyskakanie wszystkich pionków oprócz jednego? Aby to ustalić, wygodnie jest zacząć od analizy układu pionków po pierwszym skoku, którego ogólny schemat zawsze wygląda tak, jak na rys. 7 – dwa puste pola, a na prawo i/lub na lewo od nich ciąg pól z pionkami (lewego lub prawego ciągu może nie być). Zakładamy, że fragment l jest nie dłuższy niż p i rozpatrujemy kilka wariantów.
I) l=0 (brak fragmentu l), p=2 (dwa pionki) – możliwy jest jeden skok, po którym pozostaje jeden pionek;
II) l=0, p>2 lub l=1, p>1 – możliwe są tylko skoki w lewo, które prowadzą do separacji pionków (żadne dwa nie stoją na sąsiednich polach);
IIIA) l=2, p≥2 parzyste – po p/2 skokach w lewo w grupie p następuje seria 1+p/2 skoków w prawo pierwszym pionkiem z grupy l i pozostaje jeden pionek;
IIIB) l=2, p≥2 nieparzyste – w grupie p możliwe są tylko skoki parzystymi pionkami (drugim, czwartym, szóstym itd.), więc po skoku przedostatnim ostatni nieparzysty zostanie odseparowany i do końca zostanie na swoim miejscu, czyli ostatecznie na planszy pozostaną przynajmniej dwa pionki;
IV) l>2, p≥l – zakończenie z jednym pionkiem wymaga, aby między grupami l i p doszło do „współpracy”, czyli by nastąpił przeskok pionka z l przez pionek z p lub odwrotnie; jednak z powstałej po dwóch ruchach sytuacji, która taki skok umożliwia (rys. 8) wynika, że do efektywnej współpracy nie dojdzie, czyli pozostawienie jednego pionka nie będzie możliwe.
Wnioskiem z analizy wariantów jest jedyny układ po pierwszym skoku, umożliwiający wyskakanie rzędu pionków do jednego (rys. 9).
Taki układ może powstać tylko po usunięciu na wstępie pionka z drugiego lub piątego pola – licząc oczywiście z dowolnej strony rzędu – ale pod warunkiem, że rząd składa się z parzystej liczby pól. Ostatni pionek także pozostanie na polu 2 lub 5, licząc od przeciwległego końca niż ten, od którego liczono, usuwając pierwszy pionek. W przypadku nieparzystej liczby pionków jeden pionek pozostaje tylko wówczas, gdy wykonany skok jest jedynym możliwym, czyli gdy rząd składa się z trzech pionków, a na początku usuniemy pierwszy lub ostatni.
Samotnik liniowy, a także klasyczny i większość jego odmian są układami zamkniętymi, tzn. miejscem akcji jest ograniczona plansza wypełniona na początku całkowicie pionkami, z której usuwa się jeden pionek, aby móc rozpocząć rozgrywkę. Natomiast układy otwarte (przykłady na rys. 4) zajmują tylko część planszy, pozostaje więc dużo luzu – pionek na początku nie jest usuwany, tylko od razu rozpoczyna się skoki. Wiele dawnych samotnikowych zadań na klasycznych planszach to układy otwarte. Trzy przykłady na rys. 10; we wszystkich ostatni pionek powinien pozostać na centralnym polu.
W przypadku każdego układu, zarówno zamkniętego, jak i otwartego, warto na początku upewnić się, czy wyskakanie do jednego jest w ogóle możliwe, a jeśli tak, to na którym polu pozostanie ostatni pionek oraz, jeśli ustalenie tego jest możliwe, którym zacząć skoki. Prosta metoda, wykluczająca szansę zredukowania danego układu do jednego pionka, znana jest od połowy XIX wieku. Polega na dokonywaniu zmian na trzech lub czterech kolejnych polach w rzędzie, a ściślej na zastępowaniu układów pionków umieszczonych na tych polach innymi układami. Możliwe zastępstwa przedstawione są na rys. 11 – białe kółka na tym rysunku oznaczają puste pola, natomiast oba pola bez kółek w rzędzie czterech pól (dwa zastępstwa u dołu) mogą być puste lub zajęte. Jeżeli w wyniku serii zastępstw nie uda się ograniczyć całego układu do jednego pionka, to osiągnięcie takiego efektu skokami, czyli rozwiązanie zadania, również nie będzie możliwe. Dlatego nierozwiązywalny jest wspomniany wyżej kwadrat 3×3 z 9 pionków; dokonując w nim np. trzech „ekstremalnych” zastępstw, czyli usuwając trzy 3-pionkowe rzędy, likwidujemy cały układ.
Bardziej przekonująca i matematycznie ciekawsza metoda ustalania nierozwiązywalności układu jest ta z wykorzystaniem trójbarwnej szachownicy. Jeśli na takiej szachownicy umieścimy kwadratowy układ z 9 pionków (rys. 12 u góry), to na polach każdego koloru (N, B, C) znajdą się trzy pionki; cały układ możemy więc zapisać w postaci N3B3C3. Po każdym skoku-biciu układ zmniejszy się o jedno pole, a indeksy w jego zapisie zmienią się o jeden – dwa zmaleją, jeden wzrośnie; np. po skoku pionkiem z B przez N na C zapis przekształci się w N2B2C4. Istotne jest to, że po każdym skoku względna parzystość indeksów w zapisie się nie zmieni, tzn. albo wszystkie będą parzyste albo nieparzyste. Tymczasem pozostawienie jednego pionka na końcu rozgrywki oznacza, że w zapisie 1-pionkowego układu indeks, odpowiadający kolorowi tego pionka, jest nieparzysty – równy jeden, a dwa indeksy, odpowiadające pozostałym kolorom, zerowe, czyli parzyste (np. N1B0C0). Z tej sprzeczności wynika, że kwadratu 3×3 do jednego pionka wyskakać się nie da. Sprawdźmy, czy jest szansa, że uda się to z układem siedmiu pionków umieszczonym na szachownicy na rys. 12 w środku.
Zapis tego układu N3B2C2 sugeruje, że się uda, ale metoda zastępstw tego nie potwierdza; fiaskiem skończą się także próby rozwiązania. Szkopuł w tym, że układ bez poziomej i pionowej osi symetrii trzeba sprawdzić umieszczony na trójbarwnej szachownicy także w drugiej pozycji – obrócony o 90 stopni. Jeśli przynajmniej w jednej pozycji wszystkie trzy indeksy w zapisie układu są parzyste lub nieparzyste, to nie ma szans na samotnego pionka na końcu. Tak właśnie jest w przypadku układu siedmiu pionków w drugiej pozycji (rys. 12 u dołu), bo zapis ma tym razem postać N3B1C3.
Zarówno metodą zastępstw, jak i szachownicową można wykluczyć istnienie 1-pionkowego rozwiązania, ale nie potwierdzić. Niewykluczenie rozwiązania stanowi więc tylko warunek konieczny tego, by na końcu pozostał jeden pionek – zawsze na jednym z pól takiego koloru, przy którym w zapisie układu występuje indeks o innej parzystości, niż przy dwu pozostałych kolorach. Prosty warunek dostateczny rozwiązywalności nie jest znany, a skuteczna metoda, którą można by za taki warunek uznać, jest równie mozolna, jak rozwiązywanie metodą prób i błędów.
Zadania
1. Należy wyskakać do jednego 13-pionkowy układ na planszy 8×5 z rys. 5. Ruchów powinno być jak najmniej; może ich być mniej niż skoków, ponieważ dwa lub więcej kolejnych skoków tym samym pionkiem stanowi jeden ruch. Na przykład, trzeci układ na rys. 4 można wyskakać w czterech ruchach (ostatni ruch składa się z trzech skoków): 1. b4-b2, 2. d3-b3, 3. a3-c3, 4. d1-d3-b3-b1.
2. Układem jest kwadrat 4×4 złożony z 16 pionków na planszy 6×6 (rys. 13). Zaczynając od tego układu, należy wykonać jak najmniej takich ruchów, po których na planszy powstanie układ bez możliwości wykonania skoku (żadne dwa pionki nie będą umieszczone na sąsiednich polach). Jeden ruch może się składać – podobnie jak w zadaniu 1 – z dwóch lub więcej kolejnych skoków wykonanych tym samym pionkiem.
3. Pod koniec XIX wieku w Stanach Zjednoczonych opatentowana została łamigłówka „Wielka trzynastka”, czyli, niejako wbrew nazwie, minisamotnik na 13-polowej planszy. Rys. 14 przedstawia układ 10 pionków na tej planszy, a zadanie polega na wyskakaniu tego układu do jednego pionka w minimalnej liczbie ruchów. Skoki-bicia wykonywane są wzdłuż niebieskich linii, a więc także na ukos, jak w warcabach, np. z pola a1 można skoczyć na a5, c3 lub e1, z c3 na a3, c5 lub e3, a z b2 tylko na d4.
Rozwiązania prosimy nadsyłać do 31 stycznia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 1/17, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką W poszukiwaniu zera. Matematyczna odyseja do źródła pochodzenia liczb Amira D. Aczela ufundowaną przez wydawnictwo Prószyński Media.
***
Rozwiązania zadań z numeru listopadowego
1. 239; ciąg {239, 359, 479, 599, 719, 839}.
2. Rozwiązaniem zadania jest każdy z trzech ciągów: {59, 83, 107, 131}, {79, 193, 307, 421}, {97, 139, 181, 223}.
3. Rozwiązaniem są 22 początkowe liczby ciągu określonego znanym wzorem Eulera na 40 liczb pierwszych (x2+x+41 dla 0≤x≤39) – {41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503}.
Za poprawne rozwiązanie przynajmniej dwu zadań książkę Johna Gribbina Prawda ostateczna. Jak odkryliśmy narodziny Wszechświata, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Maciej Bura z Poznania, Mirosław Garnowski z Pasłęka, Łukasz Kuśmierz z Raciborza, Paweł Latosiński z Poznania, Olga Przybył z Warszawy.