LVI OM - I - Zadanie 8

Na okręgu jest umieszczonych $ n $ lampek; każda może być włączona albo wyłączona. Wykonujemy serię ruchów; w każdym ruchu wybieramy $ k $ kolejnych lampek i zmieniamy ich stan: wyłączone włączamy, a włączone wyłączamy (liczba $ k $ nie zmienia się w trakcie tego po­stępowania). Na początku wszystkie lampki są wyłączone. Dla ustalonej liczby naturalnej $ n $ wyznaczyć wszystkie liczby naturalne $ k \leq n $, dla których jest możliwe uzyskanie stanu z dokładnie jedną lampką włączoną.

Rozwiązanie

Załóżmy najpierw, że $ k $ jest liczbą parzystą. Udowodnimy indukcyjnie, że po każdej zmianie stanu $ k $ kolejnych lampek pali się parzysta liczba lampek.

Niech $ x_n $ oznacza liczbę zapalonych lampek po wykonaniu n-tego ruchu. Wówczas $ x_1 =k $. Załóżmy, że $ x_{n-1} $ jest liczbą parzystą. Jeżeli wykonując $ n $-ty ruch włączamy $ a $ lampek, a wyłączamy $ b $, to $ a+b = k $, więc $ x_n = x_{n-1} +a -b = x_{n-1} +k -2b $.

Skoro $ x_{n-1} $ i $ k $ są liczbami parzystymi, to również $ x_n $ jest liczbą parzystą. Dowód indukcyjny jest zakończony. Zatem jeśli $ k $ jest liczbą parzystą, to nie jest możliwe uzyskanie stanu z dokładnie jedną włączoną lampką.

Przyjmijmy następnie, że liczby $ n $ i $ k $ mają wspólny dzielnik $ d> 1 $ i pomalujmy lampki cyklicznie używając d kolorów. (Ściślej mówiąc, postępujemy następująco: numerujemy lampki kolejno liczbami od 1 do $ n $ poruszając się po okręgu w ustalonym kierunku, a następnie malujemy je używając $ d $ kolorów, przy czym jednakowym kolorem malujemy te lampki, których numery dają z dzielenia przez $ d $ taką samą resztę.)

Przypuśćmy, że po wykonaniu pewnego ruchu świeci się dokładnie $ s_i $ lampek $ i $-tego koloru ($ i =1,2,\ldots,d $). W każdym ruchu zmieniamy stan dokładnie $ l = k/d $ lampek $ i $-tego koloru. Jeśli włączamy $ a_i $ lampek $ i $-tego koloru, a $ b_i $ lampek i-tego koloru wyłączamy, to liczba $ s_i $ wzrasta o dokładnie $ a_i -b_i =l-2b_i $. Skoro na początku żadna lampka nie jest włączona, to po każdym ruchu liczby $ s_1,s_2,\ldots,s_d $ dają z dzielenia przez $ 2 $ taką samą resztę. Nie jest zatem możliwe uzyskanie dokładnie jednej lampki włączonej (mielibyśmy wtedy $ s_j = 1 $ dla pewnej liczby $ j $ oraz $ s_i = 0 $ dla wszystkich $ i\neq j $).

Pozostał do rozpatrzenia przypadek, gdy $ k $ jest taką liczbą nieparzystą, że $ NWD(k,n)=1 $. Warunek ten jest równoważny równości $ NWD(k,2n) = 1 $. Wykażemy, że przy pomocy rozpatrywanych ruchów można doprowadzić do sytuacji, gdy dokładnie jedna lampka jest włączona.

Stosując algorytm Euklidesa dla liczb $ k $ i $ 2n $ wnioskujemy, że istnieje taka liczba całkowita dodatnia $ x $ oraz liczba całkowita nieujemna $ y $, że

\[<br /> (1)\qquad kx-(2n)y =1 .<br /> \]

Wybieramy blok $ k $ kolejnych lampek i zmieniamy ich stan na przeciwny. Następnie wybieramy blok złożony z $ k $ lampek przyległy do poprzedniego i zmieniamy stan tych lampek na przeciwny. Procedurę kontynuujemy poruszając się po danym okręgu w ustalonym kierunku i wykonując łącznie $ x $ ruchów.

Z równości (1) wynika, że stan jednej lampki zmieni się dokładnie $ 2y +1 $ razy, a stan każdej innej dokładnie $ 2y $ razy. W efekcie dokładnie jedna lampka będzie włączona, a pozostałe wyłączone.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź