Konik szachowy Przemysław: Dzień dobry! Istnieje taka zagadka z konikiem na szachownicy − zaczynając z jakiegoś rogu szachownicy (zwykłej − 8x8) pokonać wszystkie pola, na każdym stając raz (punkt początkowy chyba zresztą nie ma znaczenia). I zastanawia mnie teraz, jak sprawdzać, czy na szachownicy o danym rozmiarze można wykonać to polecenie: przykładowo w 8x8 jest to możliwe w 6x5 też jest możliwe a w 3x3 raczej nie jest, tak jak w 1x2 czy 2x2 ale jak to sprawdzić i jak udowodnić, że nie jest coś takiego możliwe (bo, że jest możliwe, to wystarczy podać rozwiązanie). Proszę o pomoc

Kacper: Pokoloruj szachownicę Nie zastanawiałem się czy to co podałeś jest prawdą, ale prawdziwe jest zdanie. Konik startujący z rogu szachownicy 8x8 nie jest w stanie pokonać wszystkich pól, stając na każdym tylko raz, aby wylądować w przeciwległym rogu tej szachownicy.

Przemysław: To co piszesz jest prawdziwe, ale w warunkach zagadki, nie ma mowy o punkcie końcowym − możesz skończyć gdziekolwiek.

Przemysław: Więc ważne jest tylko by wszędzie stanąć dokładnie raz i ruszać się zgodnie z ruchem konika szachowego.

Kacper: Zawsze łatwiej w tych zadaniach udowodnić, że czegoś nie da się zrobić. Polecam książkę "kolorowe kwadraty" Marcina Pitery. Wciągająca lektura

Kacper: Najprościej napisać program komputerowy reprezentujący szachownice i konika szachowego i sprawdzi wszystkie opcje

Kacper: Na szachownicy 4x4 nie da się

Przemysław: Ale takie programistyczne rozwiązanie to trochę pójście na łatwiznę (w sensie matematycznym, bo trzeba to jeszcze umieć zaprogramować, a myślę że bym nie umiał). Zresztą szachownica może być duża i wtedy komputer może liczyć długo Można by faktycznie jakiegoś kolorowania poszukać. W 3x3 można powiedzieć, że a) zaczynamy w środku − nie możemy wykonać żadnego ruchu b) zaczynamy poza środkiem − nie dotrzemy do środka, bo nie ma on połączenia z żadnym z pól spoza środka ma to jakiś sens?

Przemysław: No tak wygląda, że w 4x4 się nie da, ale jak tego dowieść − bo zostaje jedno pole niepokryte, prawda?

Kacper: Konik startując z dowolnego pola musi przejść przez kropkę. Wobec tego, aby odwiedzić pola a,b,c,d,e musi 5 razy stanąć na polu z kropką. Sprzeczność Dowód nie mój.

Przemysław: Przykładowo: jeżeli startuję na f, to by zmienić literą (nie krążyć po f−f−f−f) muszę wejść na kropkę. Załóżmy, że wejdę (po kropce) na b (wykorzystałem 1/4 kropek). Zostało mi do pokonania a,c,d. Czyli 3 zmiany liter. Potrzebuję więc 3 kropek, no i mam 3 kropki. Więc czegoś nie łapię

Przemysław: Dobra − lol. Zostały mi a,c,d,e czyli 4 litery, 4 kropki, a mam 3 czyli sprzeczność

Przemysław: Dziękuję, faktycznie fajny dowód.

Przemysław: Dziękuję też za polecenie książki. Zastanawia mnie, czy można ten problem rozwiązać ogólnie, dla szachownic mxn. Np. w jakim stosunku muszą być m i n do siebie, żeby można było rozwiązać problem z zagadki.

Kacper: Tego nie wiem. Wydawać by się mogło, że dla dużych wymiarów szachownicy powinno się dać.

Przemysław: http://mathonline.wikidot.com/knight-s-tour-problem

Przemysław: Czyli w oryginalnym było jednak, że trzeba skończyć tam, gdzie się zaczęło.

daras: zajrzyj do Lilavatti Jeleńskiego

Przemysław: Dziękuję Orientujesz się, które wydanie najlepsze?

Kacper: Zapewne najmłodsze

Przemysław: Właśnie nigdy nie ma pewności, bo czasami te nowsze zawierają mniejszy materiał.

daras: najstarsze mogą się już rozsypywać

Przemysław: W każdym razie dziękuję.