Wlazł kotek na płotek ( omówienie )

08.08.2010

Pokażemy, że kotek staje na wszystkich sztachetkach tylko dla długości skoku K, dla której zachodzi nwd(K, N) == 1 ( czyli dla K względnie pierwszych z N).

Niech D = nwd(K,N).

Zaczniemy od pokazania, że dla D większych od 1 kotek nie może odwiedzić wszystkich sztachetek. Dowód:

Załóżmy, że sztachetki numerowane są od 0 do N-1, kotek zaczyna w sztachetce 0.
W dowolnym momencie nr sztachetki na której stoi kotek wyraża się liczbą 0 + liczba_skoków*K - liczba_pełnych_obejść_płotu*N. Zauważmy, że D dzieli wszystkie składniki tej sumy, więc D dzieli numer sztachetki na której stoi kotek. W takim razie kotek nigdy nie stanie na sztachetkach o numerach niepodzielnych przez D.

Pozostaje pokazać, że dla D równego 1 kotek staje na każdej sztachetce. Wystarczy pokazać, że zaczynając na sztachetce 0, kotek doskoczy do sztachetki nr 1. Dowód dostarcza nam rozszerzony algorytm Euklidesa, gwarantujący istnienie liczb liczba_pełnych_obejść_płotu i liczba_skoków, takich, że 0 + liczba_skoków*K - liczba_pełnych_obejść_płotu*N = 1.

W takim razie wystarczy policzyć nwd(K, N) dla każdego K i wypisać te względnie pierwsze z N.