Konikowo

12 listopada 2022
Marek Penszko

Na szachownicy n×n należy rozstawić k skoczków tak, aby każdy atakował inną liczbę wolnych pól – od 0 do k-1, przy czym k powinno być jak największe.
Prawie identyczne zadanie (a właściwie seria zadań dla różnych wartości n) rozpoczynało wpis zamieszczony tu 6 lat temu. Prawie, bo dotyczyło nie skoczków, tylko hetmanów. Dla obu figur istnieje n(min), czyli minimalne n, dla którego można znaleźć rozwiązanie – pomijając oczywiście trywialny przypadek n=1. Szukanie minimalnego n jest już jednak nieco innym zadaniem, bo wówczas przestaje być istotny warunek, aby k było największe. Chodzi tylko o znalezienie najmniejszej planszy n×n, na której uda się ustawić k figur tak, aby każda atakowała inną liczbę wolnych pól – od 0 do k-1.
W przypadku hetmanów tak się składa, że n(min)=3, a ustawienie figur niejako wymusza największe k=5; w dodatku jest to ustawienie ekstremalne w tym sensie, że „czwórkowy” hetman atakuje wszystkie wolne pola:

Dla skoczków plansza 3×3 jest za mała. Poniższe trzy przykładowe ustawienia czterech skoczków nie spełniają warunku, aby każdy z nich atakował inną liczbę wolnych pól – także dlatego, że na tak małej planszy konik nie może atakować 3 pól.

Ile zatem wynosi n(min) dla skoczków? Znalezienie właściwej odpowiedzi nie jest łatwe – głównie ze względu na nietypowy ruch skoczka. Z drugiej jednak strony pewnym ułatwieniem jest to, że k nie może być większe niż 9, bo konik atakuje co najwyżej 8 pól. Pewne wydaje się także umieszczenie „zerowego” skoczka w rogu planszy. Ale co dalej? Być może tutejszym mistrzom programistom uda się uporać z tym problemem, choć moim zdaniem „piechurzy” także nie są bez szans.

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.