Kółko 17 I 2004 - Irlandzka Olimpiada

1. Kwadrat magiczny 3 × 3 jest wypełniony liczbami całkowitymi dodatnimi oraz suma liczb w każdej kolumnie, w każdym wierszu i na każdej z dwóch głównych przek _{}atnych wynosi m ∈ ℤ^{+} . Wykaż, że m musi być podzielne przez 3 oraz, że najwi_{}eksza liczba wyst_{}epuj _{}aca w kwadracie jest nie wi_{}eksza niż \frac{2m}{3} − 1.

Szkic rozwi _{}azania

Oznaczmy środkow _{}a liczb_{}e przez x, zauważmy, że suma lewej kolumny i prawej kolumny oraz 3x jest równa sumie dwóch głównych przek _{}atnych oraz środkowego rz_{}edu. Zatem 2m + 3x = 3m ⇒ x = \frac{m}{3}, z czego wynika również, że pozostałe elementy musz _{}a być mniejsze niż m − \frac{m}{3} = \frac{2m}{3}.

2. Każdy wyraz ci _{}agu a_{1}, a_{2}, …, a_{n} należy do zbioru {1, 2, …, n−1} oraz a_{1}+a_{2}+…+a_{n} < 2n. Wykaż, że możemy znaleźć podci _{}ag o sumie równej n.

Szkic rozwi _{}azania

Rozpatrzmy liczby a_{1}, a_{1} + a_{2}, a_{1} + a_{2} + a_{3}, …, a_{1} + a_{2} + …+ a_{n}. Jest ich n i s _{}a w przedziale od 1 do 2n−1. Jeśli każda reszta modulo n jest przyjmowana, to jest też przyjmowana reszta 0, a jedyna taka liczba w tym przedziale to n. Jeśli nie jest przyjmowana każda reszta, to pewna reszta (z Dirichleta) jest przyjmowana minimum 2 razy, wiec różnica tych dwóch liczb daje reszt_{}e 0, czyli liczb_{}e n.

3. Ci _{}ag (a_{n}) jest zdefiniowany nast_{}epuj _{}aco: a_{1} = 1, a_{2n} = a_{n}, a_{2n+1} = a_{2n} + 1. Znajdź najwi_{}eksz _{}a wartość wśród a_{1}, a_{2}, …, a_{1989} oraz policz ile razy ona wyst_{}epuje.

Szkic rozwi _{}azania

Zauważmy, że a_{k} = ilość jedynek w rozwini_{}eciu k w systemie binarnym (można pokazać przez indukcj_{}e). Wystarczy zauważyć tylko, że maksymalna liczba jedynek w rozwini_{}eciu dwójkowym liczb do 1989 wynosi 10 i wyst_{}epuje 5 razy (liczby 1111111111, 10111111111, 11011111111, 11101111111, 11110111111 - binarnie).

4. Wykaż, że jeśli dla pewnego n ∈ ℤ^{+} zachodzi a_{n} ∈ {−1, 1} oraz a_{1}a_{2} + a_{2}a_{3} + … + a_{n−1} a_{n} + a_{n}a_{1} = 0 to 4 | n.

Szkic rozwi _{}azania

Umieścmy liczby na okr_{}egu. Zauważmy, że zmiana jednej liczby dodaje 4 (gdy po bokach s _{}a te same liczby, a ta w środku jest inna), odejmuje 4 (gdy wszystkie trzy s _{}a te same) lub nie zmienia sumy iloczynów s _{}asiednich liczb (s _{}asiedzi s _{}a różnych znaków). No a oczywiście dla samych jedynek jedynie dla n t., że 4 | n suma iloczynów jest podzielna przez 4.

5. Liczby p_{1} < p_{2} < … < p_{15} s _{}a liczbami pierwszymi tworz _{}acymi ci _{}ag arytmetyczny. Wykaż, że różnica jest wielokrotności _{}a 2 · 3 · 5 · 7 · 11 · 13.

Szkic rozwi _{}azania

Oczywiście jeśli różnica nie jest podzielna przez jakieś k z tego zbioru (2, 3, 5, 7, 11, 13), to istnieje wśród ci _{}agu (p_{n}) liczba podzielna przez k. Jeśli nie jest to 2, 3, 5, 7, to istnieje druga taka (w lewo, lub w prawo). Jeśli jest to 11 lub 13, to może tak nie być (liczba gdzieś w środku), jednak aby nie wyst _{}apiła druga taka, liczb _{}a t _{}a nie może być p_{1} (p_{1+11} i p_{1+13} należ _{}a do tego ci _{}agu). Jednak różnica ci _{}agu jest na pewno podzielna przez 2 · 3 · 5 = 30, wi_{}ec druga liczba na pewno jest wi_{}eksza niż 13.

6. Rozstrzygnać, czy istnieje taka funkcja f : ℤ^{+} → ℤ^{+} , że dla każdego n > 1 zachodzi f(n) = f(f(n − 1)) + f(f(n + 1)).

Szkic rozwi _{}azania

Nie istnieje. Zauważmy, że minimum f musi być przyjmowane dla 1, bo dla n > 1 wartość funkcji jest sum _{}a dwóch wartości tej funkcji, a wi_{}ec jest wi_{}eksze niż minimalna wartość funkcji. Niech f(1) = m. Niech k takie, że f(k) mimimum po wartościach funkcji oprócz wartości w 1. Wtedy k > 1, wi_{}ec f(k) = f(f(k − 1)) + f(f(k + 1)), czyli f(k) jest sum _{}a dwóch wartości funkcji f. Gdyby choć jedna z tych wartości była różna od m, to wtedy prawa strona byłaby wi_{}eksza od lewej, czyli musi być f(f(k − 1)) = m i f(f(k + 1)) = m. Zatem f(k + 1) = 1, bo tylko dla jedynki przyjmowane jest m. Zatem k + 1 = 1, sprzecznośc.

7. Prostok _{}at a × b, a, b ∈ ℤ^{+} podzielono na a · b małych kwadracików. Wykaż, że przek _{}atna prostok _{}ata przecina a + b − NW D(a, b) kwadracików. Oblicz ile sześcianików przecina głowna przek _{}atna w prostopadłościanie a × b × c.

Szkic rozwi _{}azania

Przek _{}atna przecina a − 1 linii pionowych i b − 1 poziomych, wi_{}ec jeśli nie przechodzi przez żaden punkt kratowy, to przecina a−1+b−1+1 = a+b−1 kwadracików. Przek _{}atna przechodzi przez NW D(a, b)−1 punktów kratowych, wi_{}ec tracimy tyle kwadracików (po jednym na każdym pkcie kratowym). Zatem wychodzi a + b + 1 − (NW D(a, b) − 1) = a + b − NW D(a, b). Dla prostopadłościanu mamy z zasady wł _{}aczeń i wył _{}aczeń a + b + c − NW D(a, b) − NW D(a, c) − NW D(b, c) + NW D(a, b, c).

8. Znajdź liczb_{}e szachownic n×n (n ∈ ℤ^{+} ustalone) wypełnionych tylko zerami i jedynkami, takich, że w każdej kolumnie i w każdym wierszu suma liczb jest nieparzysta.

Szkic rozwi _{}azania

Każd _{}a szachownic_{}e (n − 1) × (n − 1) można dopełnić do szukanej, wi_{}ec wychodzi 2^{(n−1)^{2}} .