XXXIII OM - II etap

II etap XXXIII Olimpiady Matematycznej

XXXIII OM - II - Zadanie 1

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Dowieść, że jeżeli $c, d$ są liczbami całkowitymi, przy czym $c \neq d$ , $d > 0$ to równanie

$ x^3 - 3cx^2 - dx + c = 0 $

ma nie więcej niż jeden pierwiastek wymierny.

Rozwiązanie

Zastosujemy znane twierdzenie:

Jeśli liczba wymierna zapisana w postaci ułamka nieskracalnego $\frac{p}{q}$ jest pierwiastkiem równania $a_nx^n + a_{n-1}x^{n-1} + \ldots + a_0 = 0$ o współczynnikach całkowitych to liczba $p$ jest dzielnikiem współczynnika $a_0$ , liczba $q$ jest dzielnikiem $a_n$ .

Wobec tego każdy pierwiastek wymierny równania $x^3 - 3cx^2 - dx + c = 0$ jest liczbą całkowitą dzielącą $c$ . Gdyby równanie to miało więcej niż jeden pierwiastek wymierny, na przykład liczby wymierne $q_1$ , $q_2$ byłyby pierwiastkami, to wielomian $x^3 - 3cx^2 - dx + c$ rozkładałby się na czynniki liniowe

$ (*) \qquad x^3 - 3cx^2 - dx + c = (x - q_1)(x - q_2)(x - q_3). $

Z warunku (*) wynika, że istnieje również trzeci pierwiastek wymierny $q_3$ . Pierwiastki te spełniałyby zależności

$ q_1 + q_2 + q_3 = 3c, $

$ (*) \qquad q_1q_2+ q_1q_3 + q_2q_3 = -d, $

$ q_1q_2q_3 = -c, $

(wzory Viete'a). Liczby $q_1$ , $q_2$ , $q_3$ są, jak stwierdziliśmy poprzednio, liczbami całkowitymi będącymi dzielnikami liczby $c$ , skąd wynika, że wartość bezwzględna każdej z nich nie przekracza wartości bezwzględnej liczby $c$ . Wobec tego z równania $q_1 + q_2 + q_3 = 3c$ wynika, że $q_1 = q_2 = q_3 = c$ . Ale w takim razie nie może być spełnione trzecie z równań (**) gdyż równanie $c^3 = -c$ nie ma rozwiązania w liczbach całkowitych różnych od zera. Przypuszczenie, że dane równanie ma więcej niż jeden pierwiastek wymierny doprowadziło więc do sprzeczności.

Uwaga. Założenie, że $d > 0$ nie jest istotnie i nie zostało wykorzystane w dowodzie. Teza pozostaje prawdziwa, gdy $d$ jest dowolną liczbą całkowitą. Natomiast założenie, że $c \ne 0$ jest istotne, bo na przykład równanie $x^3 - x = 0$ ma trzy pierwiastki wymierne $0$ , $1$ , $-1$ .

XXXIII OM - II - Zadanie 2

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Płaszczyznę pokryto kołami w ten sposób, że środek każdego z tych kół nie należy do żadnego innego koła. Dowieść, że każdy punkt płaszczyzny należy do co najwyżej pięciu kół.

Rozwiązanie

Przypuśćmy, że punkt $A$ należy do sześciu kół z rozważanej rodziny i że $O_1$ , $O_2$ , $O_3$ , $O_4$ , $O_5$ , $O_6$ są środkami tych kół. Wynika stąd, że pewien z kątów $O_iAO_j$ $(i,j = 1, 2, \ldots, 6)$ ma miarę nie większą od $60^\circ$ (sześć spośród kątów $O_iAO_j$ daje w sumie kąt pełny), wobec tego w trójkącie $O_iAO_j$ bok $O_iO_j$ leżący naprzeciw tego kąta nie jest bokiem najdłuższym, gdyż $O_iO_j \leq \max (AO_i,AO_j)$ . Załóżmy, że $O_iO_j \leq AO_i$ . Stąd wynika: $O_j$ należy do koła o środku $O_i$ . Przeczy to założeniu, że środek każdego z danych kół nie jest punktem żadnego innego koła. Wobec tego nie ma punktów płaszczyzny należących do więcej niż pięciu kół danej rodziny.

XXXIII OM - II - Zadanie 3

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Dowieść, że dla każdej liczby naturalnej $n \geq 2$ zachodzi nierówność

$ \log_n 2 \cdot \log_n 4 \cdot \log_n 6 \ldots \log_n (2n - 2) \leq 1. $

Rozwiązanie

Ponieważ dla liczb nieujemnych $a$ , $b$ zachodzi nierówność

$ (*) \qquad \sqrt{ab} \le \frac{a+b}{2}, $

więc dla $k = 1,2,\ldots,n$ mamy

$ \sqrt{\log_n k \cdot \log_n (2n-k)}\leq \frac{\log_n k + \log_n (2n-k)}{2} = \frac{1}{2} \log_n k(2n _ k). $

Z nierówności (*) wynika również, że

$ k(2n-k) \leq \left( \frac{k + (2n-k)}{2} \right)^2 = n^2, $

$ \frac{1}{2} \log_n k(2n-k) \leq \frac{1}{2} \log_n n^2 = \frac{1}{2} \cdot 2 =1 $

Otrzymujemy nierówności:

$ \sqrt{\log_n k \cdot \log_n (2n - k)} \leq 1, $

oraz

$ \log_n k \cdot \log_n (2n - k) \leq 1. $

Przypuśćmy, że $n$ jest liczbą nieparzystą. Łącząc w iloczynie $\log_n 2 \cdot \log_n 4 \cdot \ldots \cdot \log_n (2n - 2)$ wyraz pierwszy z ostatnim, drugi z przedostatnim itd. otrzymamy iloczyn wyrażeń postaci $\log_n k \log_n (2n - k)$ , z których każda jest na mocy poprzednich rozważań liczbą dodatnią nie większą od $1$ . Wynika stąd żądana nierówność.

Jeśli $n$ jest liczbą parzystą, to analogiczne postępowanie jak dla liczb nieparzystych prowadzi do iloczynu wyrażeń postaci $\log_n k \cdot \cdot \log_n „(2n - k)$ i czynnika $\log_n (2n - n) = \log_n n = 1$ . Zatem i w tym przypadku otrzymujemy nierówność

$ \log_n 2 \cdot \log_n 4 \cdot \ldots \cdot \log_n (2n-2) \leq 1. $

XXXIII OM - II - Zadanie 4

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Niech $A$ będzie skończonym zbiorem punktów przestrzeni mającym tą własność, że dla dowolnych jego punktów $P, Q$ istnieje izometria przestrzeni przeprowadzająca zbiór $A$ na zbiór $A$ oraz punkt $P$ na punkt $Q$ . Udowodnić że istnieje sfera przechodząca przez wszystkie punkty zbioru $A$ .

Rozwiązanie

Niech $S$ będzie środkiem ciężkości układu punktów zbioru $A$ . Każda izometria przekształcająca zbiór $A$ na zbiór $A$ przekształca też punkt $S$ na $S$ . Dla dowolnych $P, Q \in A$ izometria przekształcająca $A$ na $A$ oraz $P$ na $Q$ przekształca odcinek $\overline{PS}$ na odcinek $\overline{QS}$ . Stąd wynika, że $PS = QS$ , to jest odległości każdych dwóch punktów zbioru $A$ od punktu $S$ równe. Wobec tego wszystkie punkty zbioru $A$ leżą na pewnej sferze o środku $S$ .

XXXIII OM - II - Zadanie 5

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Niech $q$ będzie liczbą parzystą dodatnią. Dowieść, że dla każdej liczby naturalnej $n$ liczba

$ q^{(q+1)^n}+1 $

dzieli się przez $(q + 1)^{n+1}$ ale nie dzieli się przez $(q + 1)^{n+2}$ .

Rozwiązanie

Przeprowadzimy dowód indukcyjny.

Dla $n = 0$ mamy $q^{(q=1)^0} +1 = q + 1$ . Liczba ta jest podzielna przez
$(q + 1)^{0+1}$ , ale nie przez $(q + 1)^{0+2}$ .

Załóżmy, że dla pewnego $n \geq 0$ są spełnione warunki

$ (q + 1)^{n+1} \mid q^{(q+ 1)^n} \ \textrm{oraz}\ (q + 1)^{n+2} \not \mid q^{(q+1)^n} + 1, $

to jest

$ (*) \qquad q^{(q + 1)^{n}} +1 = (q+ 1)^{n+1} \cdot s, \textrm{gdzie}\ q + 1 \not \mid s. $

Należy pokazać, że również będą spełnione warunki

$ (q + 1)^{n+2} \mid q^{(q+ 1)^{n+1}}+1 \ \textrm{oraz}\ (q + 1)^{n+3} \not \mid q^{(q+1)^{n+1}} + 1. $

Dokonamy, dla parzystych liczb $q$ , następujących przekształceń stosując wzór Newtona i zależność (*).

$ \begin{split} q^{(q + 1)^{n+1}} + 1 &= q^{(q+ 1)^{n} \cdot (q+1)}+1 = [q^{(q + 1)^{n}} +1)-1]^{q+1} +1 = \\ &= [(q + 1)^{n+1}s -1]^{q+1} +1 = \sum_{j=0}^{q+1} \binom{q + 1}{j} (q+1)^{(n+1)j}s^j (-1)^{q+1-j} +1\\ &= -1 + \binom{q + 1}{1} (q + 1)^{n+1}s -\binom{q + 1}{2} (q + 1)^{2(n+1)}s^2 \\ &+ \ldots + \binom{q + 1}{q+1} (q + 1)^{(q+1)(n+1)}s^{q+1}+1 \\ &+ (q+1)(q+1)^{n+1}s - \binom{q+1}{2} (q+1)^{2(n+1)}s^2 + \ldots + (q+1)^{(q+1)(n+1)} s^{q+1}\\ &= (q+1)^{n+2} \left[ s- \binom{q+1}{2} (q+1)^n s^2 + \ldots + (q+1)^{qn+q-1} s^{q+1} \right]. \end{split} $

Suma występująca w ostatnim nawiasie kwadratowym nie dzieli się przez $q + 1$ , gdyż ze wszystkich jej składników tylko $s$ nie dzieli się przez $q + 1$ . Wobec tego otrzymamy wzory

$ (q + 1)^{n+2} \mid q^{(q+1)^{n+1}}+1, \ \textrm{ale} \ (q+1)^{n+3} \not \mid q^{(q+1)^{n+1}} + 1. $

Kończy to dowód indukcyjny.

Na mocy zasady indukcji twierdzenie jest prawdziwe dla każdej liczby całkowitej nieujemnej $n$ .

XXXIII OM - II - Zadanie 6

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Dany jest takt skończony zbiór $B$ punktów przestrzeni, że każde dwie odległości między punktami tego zbioru są różne. Każdy punkt zbioru $B$ łączymy odcinkiem z najbliższym mu punktem zbioru $B$ . Otrzymamy w ten sposób zbiór odcinków, z których jeden (dowolnie wybrany) malujemy na czerwono, wszystkie pozostałe odcinki malujemy na zielono. Dowieść, że istnieją takie dwa punkty zbioru $B$ , których nie można połączyć łamaną złożoną z odcinków pomalowanych na zielono.

Rozwiązanie

Przypuśćmy, że odcinek $A_1A_2$ jest czerwony, pozostałe są zielone. Jeśli istniałaby łamana złożona z odcinków zielonych łącząca punkty $A_1$ i $A_2$ to istniałyby punkty $A_3, \ldots, A_n$ będące kolejnymi końcami odcinków tworzących tę łamaną. Poniższy zapis typu $A_i \to A_j$ czytamy ,,najbliższym punktowi $A_i$ elementem zbioru $B$ jest $A_j$ ''. Z tego, że narysowany jest odcinek $\overline{A_iA_j}$ wynika, że $A_i \to A_j$ albo $A_j \to A_i$ . Wobec założenia, że każde dwie odległości między punktami zbioru $B$ są różne, nie może dla $k \ne j$ zachodzić jednocześnie $A_i \to A_j$ oraz $A_i \to A_k$ . Wynika stąd, że musi być albo $A_1 \to A_2, A_2 \to A_3, \ldots, A_{n-1} \to A_n, A_n \to A_1$ , albo $A_1 \to A_n, A_n \to A_{n-1}, \ldots, A_3 \to A_2, A_2 \to A_1$ .

W obu przypadkach odległości kolejnych punktów spełniałyby odpowiednio sprzeczne nierówności.

$ A_1A_2 > A_2A_3 > \ldots A_{n-1}A_n > A_nA_1 > A_1A_2 $

albo

$ A_1A_2 < A_2A_3 < \ldots < A_{n-1}A_n < A_nA_1 < A_1A_2. $

Wobec tego punkty $A_1$ i $A_2$ nie mogą być połączone łamaną złożoną z odcinków zielonych.

Uwaga. Ponieważ rozważane odcinki nie mają wspólnych punktów wewnętrznych, więc z powyższego rozwiązania wynika teza silniejsza od sformułowanej w zadaniu: Istnieją dwa punkty zbioru $B$ , których nie można połączyć łamaną złożoną z odcinków zawartych w sumie odcinków zielonych.