Osiem hetmanów, skoczek Eulera, szachownica z odciętymi rogami: najsłynniejsze matematyczne łamigłówki na szachownicy

Te łamigłówki używają figur lub siatki szachownicy, ale nie mają nic wspólnego z partią: to prawdziwe zadania matematyczne, dostępne już w gimnazjum, a niektóre zajmowały wielkie nazwiska matematyki. Są idealne na kółko matematyczne, referat lub temat prezentacji maturalnej.

Tabela zbiorcza

Problem ośmiu hetmanów

Problem ośmiu hetmanów

Ustawić osiem hetmanów na szachownicy 8 × 8 tak, by żaden nie mógł zbić innego: nigdy dwa hetmany w tym samym rzędzie, kolumnie ani na tej samej przekątnej.

Problem opublikował w 1848 roku Max Bezzel, twórca zadań szachowych. Franz Nauck podał pierwsze rozwiązania w 1850 roku i uogólnił zadanie na n hetmanów na szachownicy n × n pól. Wśród matematyków, którzy się nim zajmowali, był Carl Friedrich Gauss.

Cel zadania: znaleźć jedno ustawienie, a potem wszystkie. Jest ich 92. Wiele z nich wynika z siebie przez obrót lub symetrię szachownicy; po pogrupowaniu zostaje 12 rozwiązań podstawowych. Oto jedno z nich, z hetmanami na polach d8, g7, c6, h5, b4, e3, a2 i f1:

Łatwo sprawdzić, że w każdym rzędzie i każdej kolumnie stoi jeden hetman. Co do przekątnych wystarczy kontrolować, czy dla dowolnych dwóch hetmanów różnica kolumn nigdy nie jest równa różnicy rzędów.

Jak to rozwiązać?

Klasyczną metodą jest przeszukiwanie z nawrotami (ang. backtracking): stawiamy hetmana w pierwszej kolumnie, potem w drugiej na polu nieatakowanym, i tak dalej; gdy nie ma wolnego pola, cofamy się i przesuwamy poprzedniego hetmana. To bardzo lubiane zadanie na lekcjach informatyki w liceum. Wersja z n hetmanami ma rozwiązania dla każdego n z wyjątkiem 2 i 3: na przykład 2 rozwiązania dla n = 4, 10 dla n = 5, 4 dla n = 6, 40 dla n = 7.

Problem skoczka Eulera

Problem skoczka

Znajdź ciąg ruchów skoczka, który przechodzi dokładnie raz przez każde z 64 pól. Trasę nazywamy zamkniętą, jeśli ostatnie pole jest o jeden skok konika od pierwszego, co pozwala zacząć pętlę od nowa.

Problem jest bardzo stary: przejście skoczka po pół szachownicy pojawia się już w IX-wiecznym sanskryckim traktacie o poetyce, Kavyalankara Rudraty. Leonhard Euler poświęcił mu rozprawę „Solution d'une question curieuse qui ne paroit soumise à aucune analyse” (Rozwiązanie pewnego ciekawego pytania, które wydaje się nie poddawać żadnej analizie), przedstawioną w 1759 roku, a opublikowaną w 1766 roku w pracach Berlińskiej Akademii Nauk. W 1823 roku H. C. von Warnsdorff zaproponował prostą regułę znajdowania takiej trasy: zawsze wybieraj pole, z którego skoczek będzie miał najmniej możliwych wyjść.

Na zwykłej szachownicy istnieje ogromna liczba tras zamkniętych: 26 534 728 821 064, licząc kierunek przebiegu, czyli połowa, 13 267 364 410 532, jeśli uznać, że trasa i jej odwrotność to to samo.

Trasa do sprawdzenia na szachownicy 5 × 5

Na początek można ćwiczyć na mniejszej planszy. Oto trasa otwarta, która odwiedza wszystkie 25 pól szachownicy 5 × 5: idź za liczbami od 1 do 25, każda liczba jest o jeden skok konika od poprzedniej.

Ta trasa powstała według reguły Warnsdorffa, a każdy skok został sprawdzony. Wyzwanie: znajdź inną, która zaczyna się w środku.

Problem skoczka na maturze ustnej

Temat dobrze nadaje się na ustną część matury z matematyki rozszerzonej lub informatyki: modelowanie za pomocą grafu (pola to wierzchołki, możliwe skoki to krawędzie), szukanie ścieżki przechodzącej przez wszystkie wierzchołki, algorytm z nawrotami, reguła Warnsdorffa i jej skuteczność. Można też wyjaśnić, dlaczego na szachownicy 5 × 5 nie istnieje trasa zamknięta: skoczek zmienia kolor pola przy każdym skoku, więc pętla musi mieć parzystą liczbę pól, a 25 jest nieparzyste.

Szachownica z odciętymi rogami

Filozof Max Black postawił ten problem w 1946 roku w swojej książce Critical Thinking. Usuwamy dwa przeciwległe rogi szachownicy (na przykład a1 i h8). Czy da się pokryć pozostałe 62 pola 31 dominami, z których każda pokrywa dwa sąsiednie pola?

Odpowiedź: nie. Każda domina pokrywa koniecznie jedno pole białe i jedno czarne. 31 domin pokryłoby więc 31 pól białych i 31 czarnych. Tymczasem oba przeciwległe rogi są tego samego koloru: zostaje 32 pola jednego koloru i 30 drugiego. Wyłożenie jest niemożliwe, bez potrzeby sprawdzania choćby jednego układu. Martin Gardner upowszechnił ten problem wśród szerokiej publiczności w 1957 roku w swojej rubryce w Scientific American.

A jeśli usuniemy jedno pole białe i jedno czarne? Ralph Gomory wykazał (wynik opublikowany w 1973 roku), że wtedy wyłożenie jest zawsze możliwe, niezależnie od tego, które dwa pola usunięto.

Poliomina i pentomina

Polimino to figura złożona z identycznych kwadratów zlepionych bokami; domino ma dwa, pentomino pięć. Matematyk Solomon Golomb wprowadził i badał te figury począwszy od 1953 roku. Istnieje 12 różnych pentomin (przy założeniu, że klocek obrócony lub odwrócony pozostaje tym samym), które razem pokrywają 60 pól.

Szachownica ma 64 pola, czyli 60 + 4: można więc próbować ułożyć 12 pentomin na szachownicy, zostawiając wolny kwadrat 2 × 2 w środku. W 1958 roku Dana Scott zlecił rozwiązanie tego problemu komputerowi, będąc jednym z pierwszych zastosowań metody z nawrotami: istnieje 65 rozwiązań. Inne słynne wyzwanie: prostokąt 6 × 10 można wyłożyć 2339 różnymi sposobami za pomocą 12 pentomin.

Ile kwadratów na szachownicy?

Odpowiedź „64” jest błędna, a raczej niepełna: liczy ona tylko najmniejsze kwadraty. Trzeba doliczyć także kwadraty 2 × 2, 3 × 3… aż do dużego kwadratu 8 × 8.

Wynik to suma kwadratów liczb od 1 do 8: 1 + 4 + 9 + … + 64 = 204. Dla ciekawych: szachownica zawiera 1296 prostokątów (wliczając kwadraty), bo prostokąt wyznaczają dwa z 9 poziomych linii siatki i dwie z 9 pionowych, czyli 36 × 36.

Dalej

Te problemy wykorzystują konkretne pojęcia: parzystość, kolorowanie, zliczanie, grafy. Szczegółowo omawiamy je wraz z ćwiczeniami dla szkoły podstawowej i gimnazjum na stronie pojęcia matematyczne na szachownicy. O innych bardzo dużych liczbach przeczytasz w artykule szachownica Sissy. A jeśli lubisz zagadki, na blogu Palais des Échecs znajdziesz wyzwania logiczne Palais des Échecs, aktualizowane regularnie.