LI Olimpiada Matematyczna

Rozwiązania zadań konkursowych zawodów stopnia trzeciego

3 kwietnia 2000 r. (pierwszy dzień zawodów)

Zadanie 1.

Dana jest liczba całkowita n 2.

Wyznaczyć liczbę rozwiązań (x_{1},x_{2},...,x_{n}) układu równań

\{ \begin{matrix}x_{2} +x_{1}^{2} & & = & & 4x_{1} \\ x_{3} +x_{2}^{2} & & = & & 4x_{2} \\ x_{4} +x_{3}^{2} & & = & & 4x_{3} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ x_{n} +x_{n−1}^{2} & & = & & 4x_{n−1} \\ x_{1} +x_{n}^{2} & & = & & 4x_{n} \end{matrix}

w liczbach rzeczywistych nieujemnych.

Rozwiązanie Odpowiedź: 2^{n}. Z pierwszego równania otrzymujemy

x_{1}(x_{1}−4) = x_{1}^{2}−4x_{1} = −x_{2} 0,

skąd wynika, że x_{1} 4. Istnieje więc dokładnie jedna liczba α ∈ ⟨0,π/2⟩, spełniająca zależność x_{1} = 4sin^{2}α.

Wówczas x_{2} = x_{1}(4−x_{1}) = 4sin^{2}α·4cos^{2}α = 4sin^{2}2α. Rozumując analogicznie dostajemy

x_{k} = 4sin^{2}(2^{k−1} α) (k = 3,4,...,n)

oraz x_{1} = 4sin^{2}(2^{n}α).

Liczba rozwiązań danego układu równań w liczbach nieujemnych jest więc równa liczbie rozwiązań równania

sin^{2}α = sin^{2}(2^{n}α)

w liczbach rzeczywistych α ∈ ⟨0,π/2⟩. Ponieważ równość sinβ = ±sinγ zachodzi wtedy i tylko wtedy, gdy któraś z liczb β +γ, β −γ jest całkowitą wielokrotnością π, więc jedna z liczb (2^{n}+ 1)α, (2^{n}− 1)α musi być całkowitą wielokrotnością π. Stąd wynika, że α jest jedną z liczb:

0, \frac{kπ}{2^{n} +1} , \frac{ℓπ}{2^{n} −1} , gdzie k ∈ \{1,2,...,2^{n−1} \}, ℓ ∈ \{1,2,...,2^{n−1} − 1\} .

Ponieważ największy wspólny dzielnik liczb 2^{n} +1 i 2^{n} −1 jest równy 1, więc wyżej wypisane możliwe wartości α są różne. Zatem istnieje dokładnie 2^{n} ciągów liczb nieujemnych (x_{1},x_{2},...,x_{n}) spełniających dany układ równań.

Zadanie 2.

Dany jest trójkąt ABC, w którym AC = BC. Punkt P leży wewnątrz trójkąta ABC, przy czym < ) P AB = < ) P BC. Punkt M jest środkiem boku AB. Dowieść, że

< ) AP M +< ) BP C = 180^{∘}.

Rozwiązanie

Załóżmy najpierw, że punkt P leży wewnątrz trójkąta AMC lub na odcinku MC.

Niech Q ≠ C będzie punktem przecięcia okręgu opisanego na trójkącie BCP z prostą CM (rys. 1 i 2). Ponieważ < ) P AM = < ) P BC = < ) P QC, więc punkty A, P, M, Q leżą na jednym okręgu. Ponadto

(1)  < ) BP C = < ) BQC = < ) AQC.

A  B C P  Q M rys. 1  A  B C P Q M rys. 2

Jeżeli punkt Q znajduje się na zewnątrz trójkąta ABC (rys. 1) lub na odcinku AB, to na mocy zależności (1) otrzymujemy

< ) AP M +< ) BP C = < ) AP M +< ) AQC = 180^{∘}.

Jeżeli natomiast punkt Q znajduje się wewnątrz trójkąta ABC (rys. 2), to korzystając raz jeszcze z równości (1) uzyskujemy

< ) AP M +< ) BP C = < ) AQM +< ) AQC = 180^{∘}.

Załóżmy teraz, że punkt P znajduje się wewnątrz trójkąta BCM. Ponieważ < ) P BA = < ) P AC, więc przeprowadzając rozumowanie analogiczne do powyższego otrzymujemy równość < ) BP M +< ) AP C = 180^{∘}. Stąd

< ) AP M +< ) BP C = 180^{∘},

co kończy rozwiązanie zadania.

Zadanie 3.

Ciąg liczb naturalnych (p_{n}) spełnia następujące warunki:

1^{∘} p_{1} i p_{2} są liczbami pierwszymi,

2^{∘} dla n 3 liczba p_{n} jest największym dzielnikiem pierwszym liczby p_{n−1} +p_{n−2} +2000 .

Udowodnić, że ciąg (p_{n}) jest ograniczony.

Rozwiązanie Wykażemy najpierw, że dla dowolnego n 3 zachodzi nierówność

(1)  p_{n} max(p_{n−2} ,p_{n−1} )+2002 .

Istotnie, jeśli jedna z liczb p_{n−2} , p_{n−1} jest równa 2, to na mocy definicji, liczba p_{n} jest dzielnikiem pierwszym liczby max(p_{n−2} ,p_{n−1} )+2002. Nierówność (1) jest wtedy udowodniona. Jeśli natomiast obydwie liczby p_{n−2} , p_{n−1} są nieparzyste, to liczba p_{n} jest największym dzielnikiem pierwszym liczby parzystej p_{n−2} +p_{n−1} +2000, a więc jest także dzielnikiem pierwszym liczby

\frac{p_{n−2} +p_{n−1} +2000}{2} = \frac{p_{n−2} +p_{n−1}}{2} +1000 max(p_{n−2} ,p_{n−1} )+1000.

Zatem nierówność (1) jest spełniona również w tym przypadku.

Niech M = max(p_{1},p_{2})·2003!+2. Wykażemy indukcyjnie, że dla dowolnej liczby naturalnej n 1 zachodzi nierówność p_{n} < M.

Oczywiście p_{1} < M oraz p_{2} < M.

Załóżmy, że dla liczby naturalnej n 3 zachodzą nierówności p_{n−2} < M , p_{n−1} < M . Wówczas na mocy zależności (1) otrzymujemy p_{n} < M +2002 . Ponieważ liczby M, M+ 1, M+ 2, ..., M+ 2001 są złożone, więc w rezultacie uzyskujemy silniejsze oszacowanie: p_{n} < M.

To kończy dowód indukcyjny oraz rozwiązanie zadania.

(wp, jwr)

∗  ∗  ∗

Zadania z poprzednich Olimpiad Matematycznych oraz bieżące informacje można znaleźć w internecie pod adresem:

www.impan.gov.pl/˜ olimp/

LI Olimpiada Matematyczna

Rozwiązania zadań konkursowych zawodów stopnia trzeciego

4 kwietnia 2000 r. (drugi dzień zawodów)

Zadanie 4.

W ostrosłupie prawidłowym o wierzchołku S i podstawie A_{1}A_{2}...A_{n} każda krawędź boczna tworzy z płaszczyzną podstawy kąt 60^{∘}. Dla każdej liczby naturalnej n 3 rozstrzygnąć, czy można wybrać takie punkty B_{2},B_{3},...,B_{n} leżące odpowiednio na krawędziach A_{2}S, A_{3}S,...,A_{n}S, że

A_{1}B_{2} +B_{2}B_{3} +B_{3}B_{4} +...+B_{n−1} B_{n} +B_{n}A_{1} < 2A_{1}S.

Rozwiązanie Takie punkty istnieją dla dowolnego n 3. Niech O będzie spodkiem wysokości ostrosłupa, zaś α miarą kąta ściany

bocznej przy wierzchołku S. Z równości A_{1}S = 2A_{1}O otrzymujemy

sin \frac{α}{2} = \frac{A_{1}A_{2}}{2A_{1}S} = \frac{1}{2} · \frac{A_{1}A_{2}}{2A_{1}O} = \frac{1}{2} sin \frac{180^{∘}}{n} = sin \frac{90^{∘}}{n} cos \frac{90^{∘}}{n} < sin \frac{90^{∘}}{n} ,

skąd

(1)  nα < 180^{∘}.

Rozetnijmy powierzchnię boczną ostrosłupa wzdłuż krawędzi A_{1}S i rozłóżmy ją na płaszczyźnie. Otrzymamy wtedy wielokąt S′A′_{1}A′_{2}...A′_{n}A′′_{1}(rys. 1). Na mocy nierówności (1), < ) A′_{1}S′A′′_{1}= nα < 180^{∘}.

[figure: S′; A′_{1}; A′_{2}; A′_{3}; A′_{n−1}; A′_{n}; A′′_{1}; B′_{2}; B′_{3}; B′_{n}; ...; rys. 1]

Niech B′_{2},B′_{3},...,B′_{n} będą punktami przecięcia odcinka A′_{1}A′′_{1}odpowiednio z odcinkami A′_{2}S′,A′_{3}S′,...,A′_{n}S′. Na mocy nierówności trójkąta,

A′_{1}B′_{2}+B′_{2}B′_{3}+B′_{3}B′_{4}+...+B′_{n−1} B′_{n} +B′_{n}A′′_{1}< 2A′_{1}S′ .

Punkty B′_{2},B′_{3},...,B′_{n} wyznaczają więc punkty B_{2},B_{3},...,B_{n} na krawędziach ostrosłupa spełniające warunki zadania.

Zadanie 5.

Dla danej liczby naturalnej n 2 znaleźć najmniejszą liczbę k o następującej własności. Z dowolnego k-elementowego zbioru pól szachownicy n×n, można wybrać taki niepusty podzbiór, że liczba pól tego podzbioru w każdym wierszu i w każdej kolumnie szachownicy jest parzysta.

Rozwiązanie Udowodnimy następujące dwa zdania:

1. Z dowolnego zbioru złożonego z m+n pól szachownicy o wymiarach m×n (m,n 2) można wybrać niepusty podzbiór mający w każdym wierszu i w każdej kolumnie szachownicy parzystą liczbę pól.

2. Istnieje zbiór m+ n− 1 pól szachownicy o wymiarach m×n, z którego nie da się wybrać niepustego podzbioru mającego w każdym wierszu i w każdej kolumnie szachownicy parzystą liczbę pól.

Z powyższych zdań zastosowanych dla m = n wnioskujemy, że najmniejszą liczbą spełniającą warunki zadania jest k = 2n.

Dowód zdania 1.

Przeprowadzimy dowód indukcyjny względem m+n. Dla m = 2, n = 2 teza zdania 1 jest prawdziwa.

Ustalmy dwie liczby naturalne m, n o sumie większej niż 4 i załóżmy, że zdanie 1 jest prawdziwe dla dowolnej szachownicy o sumie wymiarów mniejszej niż m+n. Rozważmy dowolny zbiór A złożony z m+n pól szachownicy S o wymiarach m×n. Możliwe są następujące trzy przypadki:

(a) istnieje wiersz lub kolumna szachownicy S nie zawierająca żadnego pola ze zbioru A;

(b) istnieje wiersz lub kolumna szachownicy S, w której znajduje się dokładnie jedno pole ze zbioru A;

(c) w każdym wierszu i w każdej kolumnie znajdują się co najmniej dwa pola ze zbioru A.

[figure: rys. 1; rys. 2; rys. 3]

W przypadku (a) usuwamy z szachownicy S tę kolumnę (lub wiersz), która nie zawiera żadnego pola ze zbioru A. Następnie usuwamy ze zbioru A dowolne pole (na rysunku 1 pola zbioru A oznaczone są kółeczkami). W ten sposób otrzymujemy nową szachownicę, która zawiera pewien zbiór A′ złożony z m+n−1 pól i której suma wymiarów jest równa m+n−1 (rys. 2). Stąd wynika, że każdy z wymiarów uzyskanej szachownicy jest nie mniejszy niż 2. Zatem na mocy założenia indukcyjnego można wybrać ze zbioru A′ niepusty podzbiór mający w każdym wierszu i w każdej kolumnie parzystą liczbę pól. Wklejając z powrotem usuniętą kolumnę lub usunięty wiersz na swoje miejsce (rys. 3) otrzymujemy żądany podzbiór zbioru A.

Podobnie postępujemy w przypadku (b): znajdujemy najpierw kolumnę (lub wiersz), w której znajduje się dokładnie jedno pole ze zbioru A, a następnie usuwamy tę kolumnę z szachownicy S (rys. 4). W rezultacie otrzymujemy nową szachownicę, która zawiera pewien zbiór A′złożony z m+n−1 pól i której suma wymiarów jest równa m+n−1 (rys. 5). Tak jak wyżej, stosujemy założenie indukcyjne, po czym wklejamy z powrotem usuniętą kolumnę lub usunięty wiersz (rys. 6).

[figure: rys. 4; rys. 5; rys. 6]

Rozpatrzmy przypadek (c). Niech k_{1},k_{2},...,k_{n}, w_{1},w_{2},...,w_{m} oznaczają odpowiednio liczby pól zbioru A w poszczególnych kolumnach i wierszach. Wówczas

(k_{1}+k_{2}+...+k_{n})+(w_{1}+w_{2}+...+w_{m}) = 2(m+n).

Ponadto k_{i},w_{j} 2 dla wszystkich i, j. Stąd wynika, że k_{i} = w_{j} = 2. Zatem zbiór A ma w każdej kolumnie i w każdym wierszu dokładnie dwa pola. To oznacza, że liczba pól zbioru A w każdym wierszu i w każdej kolumnie jest parzysta.

Dowód indukcyjny, a tym samym dowód zdania 1, został zakończony.

Dowód zdania 2.

Rozważmy zbiór A złożony ze wszystkich m+n−1 pól szachownicy o wymiarach m×n znajdujących się w dolnym wierszu i pierwszej kolumnie (rys. 7). Aby otrzymać parzystą liczbę pól w kolumnach od drugiej do ostatniej musimy usunąć ze zbioru A pola, które się w tych kolumnach znajdują. Po ich usunięciu widzimy, że z tego samego powodu musimy usunąć pozostałe pola zbioru A. To kończy dowód zdania 2.

[figure: rys. 7]

Zadanie 6.

Stopień wielomianu P (x) o współczynnikach rzeczywistych jest nieparzysty. Ponadto dla każdego x

P (x^{2} −1) = (P (x))^{2} −1. Udowodnić, że dla każdej liczby rzeczywistej x zachodzi równość P (x) = x.

Rozwiązanie Dla dowolnej liczby rzeczywistej x prawdziwe są zależności

(P (−x))^{2} = P (x^{2}−1)+1 = (P (x))^{2}.

Stąd wynika, że dla każdego x zachodzi jedna z równości: P (−x) = P (x) lub P (−x) = −P (x).

Przypuśćmy, że dla nieskończenie wielu x zachodzi równość P (−x) = P (x). Wówczas równość ta musi być prawdziwa dla dowolnej liczby rzeczywistej x, co przeczy założeniu, że stopień wielomianu P jest liczbą nieparzystą.

Zatem dla nieskończenie wielu x zachodzi równość P (−x) = −P (x), skąd wynika, że równość ta jest prawdziwa dla wszystkich liczb rzeczywistych x.

Dowolną liczbę rzeczywistą x −1 możemy zapisać w postaci x = y^{2}−1, dla pewnej liczby rzeczywistej y. Stąd

(1)  P (x) = P (y^{2}−1) = (P (y))^{2}−1 −1 .

Określamy rekurencyjnie ciąg (x_{n}) wzorami:

x_{1} = 1 oraz x_{n} = \sqrt{x_{n−1} +1} dla n 2 .

Udowodnimy indukcyjnie, że

(2)  P (x_{n}) = x_{n} dla n ∈ ℕ.

Z zależności P (−x) = −P (x) otrzymujemy P (0) = 0. Kładąc x = 0 do danej w treści zadania tożsamości otrzymujemy P (−1) = −1, skąd P (1) = 1. To dowodzi równości (2) dla n = 1.

Ze związku P (x_{n−1} ) = x_{n−1} wynika, że

(P (x_{n}))^{2} = P (x_{n}^{2} −1)+1 = P (x_{n−1} )+1 = x_{n−1} +1 = x_{n}^{2} .

Ponieważ x_{n} > 1 dla n 2, więc nierówność (1) wyklucza prawdziwość równości P (x_{n}) = −x_{n} . Zatem P (x_{n}) = x_{n}, co kończy dowód zależności (2).

Ciąg (x_{n}) jest rosnący, więc równość P (x) = x zachodzi dla nieskończenie wielu x. Z tego zaś wynika, że P (x) = x dla wszystkich x ∈ ℝ.

(wp, jwr)

∗  ∗  ∗

Zadania z poprzednich Olimpiad Matematycznych oraz bieżące informacje można znaleźć w internecie pod adresem:

www.impan.gov.pl/˜ olimp/