Polowanie na króla?

20 listopada 2021
Marek Penszko

Na szachownicy nxn stoi król. Założył czapkę-niewidkę, więc nie wiadomo, na którym polu przycupnął. Ustalenie miejsca pobytu króla powierzono hetmanowi, który powinien się z tym uporać, zajmując w kolejnych ruchach odpowiednie pola. Pierwszy ruch jest umieszczeniem hetmana na dowolnym polu, a każdy następny polega na przesunięciu go na wybrane pole zgodnie z hetmańskim sposobem przemieszczania się. Po każdym umiejscowieniu hetmana podawana jest jedna z trzech informacji: szach, mat lub pudło. Szach – wiadomo – oznacza, że hetman atakuje króla, mat – że stanął na królewskim polu, czyli przypadkiem wpadł na króla, więc uporał się z zadaniem, pudło – na żadnym polu atakowanym przez hetmana nie ma króla. Pytanie brzmi: najpóźniej w którym ruchu genialny, czyli logicznie myślący hetman jest w stanie uporać się z zadaniem?
Gdy n=1, to król nie ma wyboru zatem hetman nie ma nic do roboty, czyli x (liczba ruchów) = 0. Dla n=2 każdy ruch oznacza szach lub mat. Pudeł brak, więc wnioskować nie ma z czego. Najdalej po trzech szachach, król zostanie zlokalizowany, zatem x=3. Od n=3 sprawa nieco się komplikuje, aczkolwiek w tym przypadku jeszcze dość łatwo ustalić, że hetmanowi także wystarczą 3 ruchy. A iloruchowy trud czeka hetmana przy n=4 i n=5 (nie wspominając o większych n)?

Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.