Czy istnieje zamknięta lub otwarta ścieżka skoczka?

[kylercopeland]

Czy istnieje zamknięta lub otwarta ścieżka skoczka na szachownicy 4x4 i 5x5 dla dowolnych wierzchołków początkowych?

Dokopałem się do pracy Schwenka "Which Rectangular Chessboards Have a Knight's Tour?" z 1991 r. Udało mi się wywnioskować, że dla 4x4 nie istnieje otwarta ani zamknięta ścieżka skoczka, a dla 5x5 istnieje otwarta, a nie istnieje zamknięta - ale generalnie nie wiem jak to udowodnić.

W przypadku 5x5 ścieżki zamkniętej dowód jest prosty. Przekształcamy szachownicę na graf, gdzie wierzchołki to pola, a krawędzie to możliwe ruchy skoczka. Otrzymujemy graf dwudzielny. 5x5=25 więc liczba nieparzysta, a cykl o nieparzystej długości w grafie dwudzielnym nie może istnieć.

Co do 4x4 ścieżki zamkniętej, kompletnie nie rozumiem przedstawionego tam dowodu. Oto on:

"Załóżmy, że znaleźliśmy cykl. Pokolorujmy wierzchołki w pierwszym i czwartym wierszu na czerwono, a w drugim i trzecim na niebiesko. Takie pokolorowanie nie stanowi już grafu dwudzielnego, ponieważ niektóre niebieskie wierzchołki połączone są z innymi niebieskimi. Aczkolwiek każdy czerwony połączony jest tylko z niebieskimi. W cyklu każdy wierzchołek czerwony musi być rozdzielony niebieskim. Skoro mamy 8 wierzchołków każdego koloru to wierzchołki w cyklu muszą być naprzemiennie. Zaczynając od wierzchołka (1,1) możemy wywnioskować że każdy wierzchołek na nieparzystym miejscu w cyklu jest czerwony. Ale z oryginalnego pokolorowania szachownicy na czarno i biało możemy wywnioskować że każdy wierzchołek na nieparzystym miejscu w cyklu jest biały. Zatem wszystkie czerwone wierzchołki są wierzchołkami białymi, co prowadzi do sprzeczności między wybranymi dwoma sposobami kolorowań. Dochodzimy do wniosku, że cykl nie istnieje."

Nie rozumiem wniosków od momentu "Ale z oryginalnego pokolorowania...".
Pozostaje jeszcze kwestia ścieżki otwartej 4x4 i 5x5, o której praca niestety nie wspomina.

Proszę o pomoc.

[bakala12]

Okej rozwieję wątpliwości. Dla tablicy 4x4 nie ma ścieżki otwartej (i co za tym idzie zamkniętej też nie ma). Z dowodem trzeba by pokombinować.

Ponumerujmy szachownicę kolejnymi liczbami:
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|}
\hline
0 & 1 & 2 & 3 & 4 \\
\hline
5 & 6 & 7 & 8 & 9 \\
\hline
10 & 11 & 12 & 13 & 14 \\
\hline
15 & 16 & 17 & 18 & 19 \\
\hline
20 & 21 & 22 & 23 & 24 \\
\hline
\end{tabular}}\)

Przykładowa ścieżka jest następująca:
\(\displaystyle{ 8,1,10,21,12,19,22,15,6,3,14,23,16,5,2,9,18,7,0,11,20,17,24,13,4}\)
Wszystkich ścieżek na takiej szachownicy ponumerowanej (tj. nie uwzględniając obrotów itd.) jest 4736. Można je wyznaczyć algorytmem z nawrotami.