- LX OM
- LIX OM
- LVIII OM
- LVII OM
- LVI OM
- LV OM
- LIV OM
- LIII OM
- LII OM
- LI OM
- L OM
- XLIX OM
- XLVIII OM
- XLVIII OM - I etap
- XLVIII OM - I - Zadanie 1
- XLVIII OM - I - Zadanie 2
- XLVIII OM - I - Zadanie 3
- XLVIII OM - I - Zadanie 4
- XLVIII OM - I - Zadanie 5
- XLVIII OM - I - Zadanie 6
- XLVIII OM - I - Zadanie 7
- XLVIII OM - I - Zadanie 8
- XLVIII OM - I - Zadanie 9
- XLVIII OM - I - Zadanie 10
- XLVIII OM - I - Zadanie 11
- XLVIII OM - I - Zadanie 12
- XLVIII OM - II etap
- XLVIII OM - III etap
- XLVIII OM - I etap
- XLVII OM
- XLVI OM
- XLV OM
- XLIV OM
- XLIII OM
- XLII OM
- XLI OM
- XL OM
- XXXIX OM
- XXXVIII OM
- XXXVIII OM - I etap
- XXXVIII OM - I - Zadanie 1
- XXXVIII OM - I - Zadanie 2
- XXXVIII OM - I - Zadanie 3
- XXXVIII OM - I - Zadanie 4
- XXXVIII OM - I - Zadanie 5
- XXXVIII OM - I - Zadanie 6
- XXXVIII OM - I - Zadanie 7
- XXXVIII OM - I - Zadanie 8
- XXXVIII OM - I - Zadanie 9
- XXXVIII OM - I - Zadanie 10
- XXXVIII OM - I - Zadanie 11
- XXXVIII OM - I - Zadanie 12
- XXXVIII OM - II etap
- XXXVIII OM - III etap
- XXXVIII OM - I etap
- XXXVII OM
- XXXVII OM - I etap
- XXXVII OM - I - Zadanie 1
- XXXVII OM - I - Zadanie 2
- XXXVII OM - I - Zadanie 3
- XXXVII OM - I - Zadanie 4
- XXXVII OM - I - Zadanie 5
- XXXVII OM - I - Zadanie 6
- XXXVII OM - I - Zadanie 7
- XXXVII OM - I - Zadanie 8
- XXXVII OM - I - Zadanie 9
- XXXVII OM - I - Zadanie 10
- XXXVII OM - I - Zadanie 11
- XXXVII OM - I - Zadanie 12
- XXXVII OM - II etap
- XXXVII OM - III etap
- XXXVII OM - I etap
- XXXVI OM
- XXXV OM
- XXXIV OM
- XXXIII OM
- XXXIII OM - I etap
- XXXIII OM - I - Zadanie 1
- XXXIII OM - I - Zadanie 2
- XXXIII OM - I - Zadanie 3
- XXXIII OM - I - Zadanie 4
- XXXIII OM - I - Zadanie 5
- XXXIII OM - I - Zadanie 6
- XXXIII OM - I - Zadanie 7
- XXXIII OM - I - Zadanie 8
- XXXIII OM - I - Zadanie 9
- XXXIII OM - I - Zadanie 10
- XXXIII OM - I - Zadanie 11
- XXXIII OM - I - Zadanie 12
- XXXIII OM - II etap
- XXXIII OM - III etap
- XXXIII OM - I etap
- XXXII OM
- XXXI OM
- XXX OM
- XXIX OM
- XXVIII OM
- XXVII OM
- XXVI OM
- XXV OM
- XXIV OM
- XXIII OM
- XXII OM
- XXI OM
- XX OM
- XIX OM
- XVIII OM
- XVII OM
- XVI OM
- XV OM
- XIV OM
- XIII OM
- XII OM
- XI OM
- X OM
- IX OM
- VIII OM
- VII OM
- V OM
- VI OM
- IV OM
- III OM
- II OM
- I OM
- Skład komitetów Olimpiady
- Zawody stopnia I (przygotowawcze)
- Zadania z pierwszej olimpiady matematycznej
- I OM - B
- I OM - B - Zadanie 1
- I OM - B - Zadanie 2
- I OM - B - Zadanie 3
- I OM - B - Zadanie 4
- I OM - B - Zadanie 5
- I OM - B - Zadanie 6
- I OM - B - Zadanie 7
- I OM - B - Zadanie 8
- I OM - B - Zadanie 9
- I OM - B - Zadanie 10
- I OM - B - Zadanie 11
- I OM - B - Zadanie 12
- I OM - B - Zadanie 13
- I OM - B - Zadanie 14
- I OM - B - Zadanie 15
- I OM - B - Zadanie 16
- I OM - B - Zadanie 17
- I OM - B - Zadanie 18
- I OM - B - Zadanie 19
- I OM - B - Zadanie 20
- I OM - I etap
- I OM - II etap
- I OM - III etap
- I OM - B
LVI OM - I - Zadanie 8
Na okręgu jest umieszczonych lampek; każda może być włączona albo wyłączona. Wykonujemy serię ruchów; w każdym ruchu wybieramy
kolejnych lampek i zmieniamy ich stan: wyłączone włączamy, a włączone wyłączamy (liczba
nie zmienia się w trakcie tego postępowania). Na początku wszystkie lampki są wyłączone. Dla ustalonej liczby naturalnej
wyznaczyć wszystkie liczby naturalne
, dla których jest możliwe uzyskanie stanu z dokładnie jedną lampką włączoną.
Rozwiązanie
Załóżmy najpierw, że jest liczbą parzystą. Udowodnimy indukcyjnie, że po każdej zmianie stanu
kolejnych lampek pali się parzysta liczba lampek.
Niech oznacza liczbę zapalonych lampek po wykonaniu n-tego ruchu. Wówczas
. Załóżmy, że
jest liczbą parzystą. Jeżeli wykonując
-ty ruch włączamy
lampek, a wyłączamy
, to
, więc
.
Skoro i
są liczbami parzystymi, to również
jest liczbą parzystą. Dowód indukcyjny jest zakończony. Zatem jeśli
jest liczbą parzystą, to nie jest możliwe uzyskanie stanu z dokładnie jedną włączoną lampką.
Przyjmijmy następnie, że liczby i
mają wspólny dzielnik
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
poruszając się po okręgu w ustalonym kierunku, a następnie malujemy je używając
kolorów, przy czym jednakowym kolorem malujemy te lampki, których numery dają z dzielenia przez
taką samą resztę.)
Przypuśćmy, że po wykonaniu pewnego ruchu świeci się dokładnie lampek
-tego koloru (
). W każdym ruchu zmieniamy stan dokładnie
lampek
-tego koloru. Jeśli włączamy
lampek
-tego koloru, a
lampek i-tego koloru wyłączamy, to liczba
wzrasta o dokładnie
. Skoro na początku żadna lampka nie jest włączona, to po każdym ruchu liczby
dają z dzielenia przez
taką samą resztę. Nie jest zatem możliwe uzyskanie dokładnie jednej lampki włączonej (mielibyśmy wtedy
dla pewnej liczby
oraz
dla wszystkich
).
Pozostał do rozpatrzenia przypadek, gdy jest taką liczbą nieparzystą, że
. Warunek ten jest równoważny równości
. 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 i
wnioskujemy, że istnieje taka liczba całkowita dodatnia
oraz liczba całkowita nieujemna
, że
![]() |
Wybieramy blok kolejnych lampek i zmieniamy ich stan na przeciwny. Następnie wybieramy blok złożony z
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
ruchów.
Z równości (1) wynika, że stan jednej lampki zmieni się dokładnie razy, a stan każdej innej dokładnie
razy. W efekcie dokładnie jedna lampka będzie włączona, a pozostałe wyłączone.
Komentarze
Dodaj nową odpowiedź