Hetmania
Na szachownicy n×n należy rozstawić k hetmanów tak, aby każdy atakował inną liczbę wolnych pól od 0 do k-1, przy czym k powinno być jak największe. Pomijając trywialny przypadek „szachownicy” 1×1, najmniejszą, na której zadanie ma rozwiązanie, jest plansza 3×3:
Rozwiązanie na takiej mini-szachownicy jest ekstremalne, tzn. jeden z hetmanów atakuje wszystkie wolne pola (4), a więc k=(n^2+1)/2. Dla planszy 4×4 (chyba) i dla większych plansz (na pewno) takie ekstremalne rozwiązania nie istnieją.
Zadanie zamieszczone we wrześniowym Świecie Nauki dotyczyło konkretnego przypadku – szachownicy 5×5. Jeden z czytelników zaskoczył mnie stwierdzeniem, że zadanie jest niewykonalne, co wsparł dowodem wspomaganym komputerowo. W rzeczywistości jest dokładnie odwrotnie – zadanie ma więcej niż jedno rozwiązanie. Oto jedno z nich.
Kto znajdzie całkiem inne rozwiązanie z 11 hetmanami (12 na pewno nie da się ustawić)? „Całkiem” oznacza, że wykluczamy obroty i odbicia, ale wystarczy, aby jeden hetman był umieszczony gdzie indziej (tak mała zmiana nie jest jednak możliwa). Niezmienna pozostać musi narożna pozycja „zerowego” hetmana i trzech, tworzących jego obstawę.
Komentarze
Jest 6 istotnie różnych rozwiązań. Poniżej jest 12 bo mamy symetrie względem głównej przekątnej.
Druga cyfra w długiej linijce (przed pierwszą gwiazdką) to numer rozwiązania.
Pary (numer rozwiazania, numer rozw. symetrycznego):
(1,5)
(2,9)
(3,11)
(4,12)
(6,8)
(7,10)
A to rozwiązania na szachownicy. (1-hetman, 2-puste pole). Resztę treści w długich liniach ignorujemy 🙂
0,1,”*”,11,”*”,2,4,9,5,8,10,7,6,1,3,0
1,1,1,1,2
1,1,2,1,1
1,2,2,2,2
2,2,1,2,2
2,1,2,2,2
0,2,”*”,11,”*”,2,6,5,10,8,7,9,4,1,3,0
1,1,1,1,2
1,1,2,2,2
2,1,1,2,1
1,2,2,2,2
2,2,2,1,2
0,3,”*”,11,”*”,5,4,6,10,9,3,8,7,2,1,0
1,1,1,1,2
1,1,2,2,2
2,1,2,1,2
2,1,2,2,2
1,2,1,2,2
0,4,”*”,11,”*”,4,1,9,5,8,10,3,7,6,2,0
1,1,1,2,1
1,1,2,1,1
2,2,2,2,2
2,2,2,2,1
2,2,1,2,1
0,5,”*”,11,”*”,8,7,2,10,4,9,5,6,3,1,0
1,1,1,2,2
1,1,2,2,1
1,2,2,1,2
1,1,2,2,2
2,1,2,2,2
0,6,”*”,11,”*”,8,10,4,9,6,7,3,5,1,2,0
1,1,1,2,2
1,1,2,2,2
2,1,2,2,2
1,2,2,1,1
1,2,2,2,1
0,7,”*”,11,”*”,2,3,5,6,10,8,9,7,4,1,0
1,1,2,1,1
1,1,1,1,2
2,2,2,1,2
1,2,2,2,2
2,2,2,2,1
0,8,”*”,11,”*”,4,7,10,8,9,6,3,5,2,1,0
1,1,2,1,1
1,1,1,2,2
1,2,2,2,2
2,2,2,1,2
2,2,2,1,1
0,9,”*”,11,”*”,7,5,2,10,6,9,8,4,3,1,0
1,1,2,1,2
1,1,1,2,2
1,2,1,2,2
1,2,2,2,1
2,2,1,2,2
0,10,”*”,11,”*”,8,5,2,6,10,3,9,7,1,4,0
1,1,2,1,2
1,1,2,2,2
2,1,2,2,2
1,1,1,2,2
1,2,2,2,1
0,11,”*”,11,”*”,3,6,9,5,8,4,10,7,1,2,0
1,1,2,2,1
1,1,1,1,2
1,2,2,2,1
1,2,1,2,2
2,2,2,2,2
0,12,”*”,11,”*”,4,10,9,1,5,8,3,7,2,6,0
1,1,2,2,2
1,1,2,2,2
1,2,2,2,1
2,1,2,2,2
1,1,2,1,1
Znalazłem 6 istotnie różnych ustawień 11 hetmanów na planszy 5×5 (liczba oznacza liczbę atakowanych pól, A to 10):
-6230
—41
8-A5-
—-7
-9—
74-10
–A52
—-8
-9—
36—
32-10
-6574
-A—
—-8
9—-
15-83
-9—
4—A
27—
06—
02–3
1769-
5—8
4-A–
—–
018–
36–7
2–A-
49—
-5—
Jeszcze raz, bo poprzedni wpis wygląda tragicznie (formatowanie):
_6230
___41
8_A5_
____7
_9___
74_10
__A52
____8
_9___
36___
32_10
_6574
_A___
____8
9____
15_83
_9___
4___A
27___
06___
02__3
1769_
5___8
4_A__
_____
018__
36__7
2__A_
49___
_5___