XXXV OM - II etap

II etap XXXV Olimpiady Matematycznej

XXXV OM - II - Zadanie 1

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Dla danej liczby naturalnej $n$ znaleźć liczbę rozwiązań równania $\sqrt{x} + \sqrt{y} = n$ w liczbach naturalnych $x, y$ .

Rozwiązanie

Dla $n = 1$ dane równanie nie ma rozwiązań w liczbach naturalnych. Dla $n > 1$ każda para liczb $x_1 = 1^2, y_1 = (n- 1)^2, x_2 = 2^2, y_2 = (n-2)^2, \ldots, x_{n-1} = (n - 1)^2, y_{n-1} = 1^2$ stanowi oczywiście rozwiązanie danego równania, gdyż $\sqrt{k^2} + \sqrt{(n - k)^2} = k+(n-k) = n$ dla $0 < k < n$ .

Wykażemy, że innych rozwiązań nie ma. Gdyby para liczb naturalnych $x$ , $y$ była rozwiązaniem danego równania, przy czym np. liczba $x$ nie byłaby kwadratem liczby naturalnej, to spełniona byłaby równość $y = (n -\sqrt{x})^2$ , skąd wynikałoby, że $y-n^2 - x = 2n\sqrt{x}$ . Po lewej stronie tej równości występuje liczba całkowita, zatem $2n \sqrt{x}$ również jest liczbą całkowitą. Zatem $\sqrt{x}$ jest liczbą wymierną, $\sqrt{x} = \frac{m}{n}$ . Wobec tego $x = \left( \frac{m}{n} \right)^2$ , $xn^2 = m^2$ . W rozkładzie liczb $n^2$ , $m^2$ na czynniki pierwsze każdy czynnik występuje w potędze o wykładniku parzystym. Wobec jednoznaczności rozkładu liczby naturalnej na czynniki pierwsze wynika stąd, że również w rozkładzie liczby $x$ każdy czynnik pierwszy występuje w potędze o wykładniku parzystym,

$ x = p_1^{2k_1} p_2^{2k_2} \ldots p_s^{2k_s} $

Zatem $x$ jest kwadratem liczby naturalnej wbrew założeniu. Podobnie stwierdzamy,że żadna para liczb naturalnych $(x, y)$ , w której $y$ nie jest kwadratem liczby naturalnej, nie jest rozwiązaniem danego równania.

Wobec tego dane równanie ma $n - 1$ rozwiązań w liczbach naturalnych.

XXXV OM - II - Zadanie 2

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Na bokach trójkąta $ABC$ budujemy podobne trójkąty równoramienne: trójkąt $APB$ na zewnątrz trójkąta $ABC$ ( $AP = PB$ ), trójkąt $CQA$ na zewnątrz trójkąta $ABC$ ( $CQ = QA$ ), trójkąt $CRB$ do wewnątrz trójkąta $ABC$ ( $CR = RB$ ). Dowieść, że $APRQ$ jest równoległobokiem lub punkty $A, P, R, Q$ leżą na prostej.

Rozwiązanie

Rozważmy podobieństwo mające punkt stały $C$ i przekształcające $B$ na $R$ (jest to złożenie obrotu wokół $C$ o kąt $BCR$ z jednokładnością o środku $C$ i skali równej stosunkowi długości podstawy do długości ramienia w każdym ze zbudowanych trójkątów równoramiennych). Podobieństwo to przekształca $A$ na $Q$ . Wynika stąd, że trójkąty $ABC$ i $QRC$ są podobne.

Analogicznie stwierdzamy, że podobieństwo o punkcie stałym $B$ przekształcające $C$ na $R$ przekształca $A$ na $P$ , więc trójkąty $ABC$ i $PBR$ są podobne. Wobec tego trójkąty $QRC$ i $PBR$ są podobne. Ponieważ $BR = CR$ , więc trójkąty te są przystające, a zatem $QC = PR$ i $QR = PB$ . Ale $QC = AQ$ i $PB = AP$ , więc $AQ = PR$ i $AP = QR$ . Ponadto kąt między wektorami $\overrightarrow{BP}$ i $\overrightarrow{RQ}$ ma miarę równą $\measuredangle PBA + \measuredangle BCR = 2 \measuredangle PBA$ , kąt zaś między wektorami $\overrightarrow{AP}$ i $\overrightarrow{BP}$ ma miarę równą $180^\circ - 2 \measuredangle PBA$ , skąd wynika, że wektory $\overrightarrow{RQ}$ i $\overrightarrow{AP}$ są równoległe. Wobec tego punkty $A$ , $P$ , $R$ , $Q$ leżą na jednej prostej albo są kolejnymi wierzchołkami równoległoboku.

XXXV OM - II - Zadanie 3

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Dane są ciągi $(x_1, x_2, \ldots, x_n)$ , $(y_1, y_2, \ldots, y_n)$ o wyrazach dodatnich. Udowodnić, że istnieje taka permutacja $p$ zbioru $\{1, 2, \ldots, n\}$ , że dla każdego rzeczywistego $t$ ciąg

$ (x_{p(1)}+ty_{p(1)}, x_{p(2)}+ty_{p(2)}, \ldots, x_{p(n)}+ty_{p(n)}) $

ma następującą własność: istnieje taka liczba $k$ , że $1 \leq k \leq n$ oraz wszystkie niezerowe wyrazy ciągu o wskaźnikach mniejszych od $k$ są jednakowego znaku i wszystkie niezerowe wyrazy ciągu o wskaźnikach nie mniejszych od $k$ są jednakowego znaku.

Rozwiązanie

Obliczamy ilorazy $\frac{x_1}{y_1}, \frac{x_2}{y_2}, ldots, \frac{x_n}{y_n}$ , znajdujemy takie $j$ , że $\frac{x_j}{y_j}$ jest nie większe od wszystkich pozostałych ilorazów i przyjmujemy $p(1) = j$ . Następnie znajdujemy takie $k$ , że $\frac{x_k}{y_k}$ jest nie większe od wszystkich ilorazów $\frac{x_i}{y_i}$ różnych od $\frac{x_j}{y_j}$ i przyjmujemy $p(2) = k$ itd.

Wobec tego

$ \frac{x_{p(1)}}{y_{p(1)}} \leq \frac{x_{p(2)}}{y_{p(2)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}}. $

Rozważamy dowolną liczbę rzeczywistą $t$ i porównujemy liczbę $- t$ z liczbami $\frac{x_{p(j)}}{y_{p(j)}}$ . Istnieje liczba naturalna $k$ , dla której

$ (*) \qquad \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(k-1)}}{y_{p(k-1)}} \leq-t \leq \frac{x_{p(k)}}{y_{p(k)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}} $

przy czym może być $k = 1$ , tj.

$ -t \leq \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}}, $

albo $k = n +1$ , tj.

$ \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}} \leq -t, $

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

$ \frac{x_{p(1)}}{y_{p(1)}} +t \leq 0, \ldots, \frac{x_{p(k-1)}}{y_{p(k-1)}} +t\leq 0, \frac{x_{p(k)}}{y_{p(k)}}+t \geq 0,\ldots, \frac{x_{p(n)}}{y_{p(n)}}+t \geq 0, $

a ponieważ $y_{p(i)} > 0$ dla $i = 1,\ldots,n$ , więc

$ x_{p(1)}+ty_{p(1)} \leq 0, \ldots, x_{p(k-1)} + ty_{p(k-1)} \leq 0, x_{p(k)}+ty_{p(k)} \geq 0, \ldots, x_{p(n)} +ty_{p(n)} \geq 0 $

co kończy dowód.

Uwaga. W dowodzie wykorzystaliśmy jedynie dodatniość wyrazów ciągu $(y_i)$ .

XXXV OM - II - Zadanie 4

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

W zawodach Olimpiady Matematycznej bierze udział $3n$ uczestników. Mają oni wyznaczone miejsca w trzech rzędach, po $n$ miejsc w każdym i są wpuszczani na salę pojedynczo, po czym natychmiast zajmują swoje miejsca. Obliczyć prawdopodobieństwo tego, że aż do momentu zajęcia miejsca przez ostatniego zawodnika, w każdej chwili dla każdych dwóch rzędów różnica liczb siedzących w nich zawodników jest nie większa od 1.

Rozwiązanie

Zdarzeniami elementarnymi są permutacje zbioru $3n$ -elementowego. Liczba ich wynosi $(3n)!$ . Obliczymy liczbę zdarzeń sprzyjających zdarzeniu wymienionemu w treści zadania. Jako pierwszy może wyjść na salę dowolny zawodnik (jest więc $3n$ możliwości). Następna osoba może być jedną z $2n$ tych, których miejsca nie są wyznaczone w rzędzie, w którym siedzi pierwszy zawodnik. Trzecim wchodzącym na salę uczestnikiem powinien być ktoś mający miejsce w rzędzie, w którym nie siedzi żaden z poprzednio wpuszczonych zawodników (jest $n$ takich możliwości). Następną osobą może być ktokolwiek z pozostałych $3(n -1)$ osób. Kolejna osoba nie może usiąść w rzędzie, w którym siedzą już dwie osoby, jest więc $2(n- 1)$ możliwości wyboru tego zawodnika. Szósta osoba wpuszczana na salę powinna być jedną z $n - 1$ osób, których miejsce jest w rzędzie zajętym tylko przez jednego zawodnika. Następnie sytuacja znów się powtarza: we wszystkich rzędach siedzą po dwie osoby, przed wejściem czeka $3 (n - 2)$ zawodników. Teraz może wejść którykolwiek z nich, po nim ktoś z $2(n - 2)$ tych, których miejsca są w innych rzędach niż miejsce ostatnio wpuszczonego itd. Liczba zdarzeń sprzyjających wynosi więc

$ \begin{split} 3n \cdot 2n \cdot n \cdot 3 (n - 1) \cdot 2 (n - 1) \cdot (n - 1) \cdot 3 (n - 2) \cdot 2 (n - 2) \cdot (n - 2) \ldots 3 \cdot 2 \cdot 1 =\\ = 3n \cdot 3(n-1) \cdot 3(n-2) \cdot \ldots \cdot 3 \cdot 2n \cdot 2(n-1) \cdot 2(n-2) \cdot \ldots \cdot 2 \cdot n \cdot (n-1) \cdot (n-2) \cdot \ldots 1 =\\ = 3^n \cdot n! \cdot 2^n \cdot n! \cdot n! = 6^n \cdot (n!)^3 \end{split} $

(Podany tu opis można oczywiście zastąpić dowodem indukcyjnym). Wobec tego szukane prawdopodobieństwo wynosi

$ \frac{6^n \cdot (n!)^3}{(3n)!} $

XXXV OM - II - Zadanie 5

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Obliczyć kres dolny pól sześciokątów wypukłych, których wszystkie wierzchołki mają współrzędne całkowite.

Rozwiązanie

W rozwiązaniu zastosujemy następujący lemat, który był treścią zadania konkursowego w poprzedniej Olimpiadzie Matematycznej

Lemat. Podwojone pole trójkąta, którego wszystkie wierzchołki mają współrzędne całkowite jest liczbą całkowitą.

Dowód. Pole trójkąta $ABC$ jest równe połowie wartości bezwzględnej
wyznacznika utworzonego ze współrzędnych wektorów $\overrightarrow{AB}$ i $\overrightarrow{AC}$ . Jeśli współrzędne wierzchołków $A$ , $B$ , $C$ są liczbami całkowitymi, to współrzędne wektorów $\overrightarrow{AB}$ i
$\overrightarrow{AC}$ też są liczbami całkowitymi, wyznacznik utworzony z tych współrzędnych również jest liczbą całkowitą, a w konsekwencji podwojone pole trójkąta $ABC$ jest liczbą całkowitą.

Każdy punkt na płaszczyźnie mający współrzędne całkowite należy do dokładnie jednego z następujących czterech zbiorów

$A$ - zbiór punktów, których obie współrzędne są parzyste,
$B$ - zbiór punktów, których obie współrzędne są nieparzyste,
$C$ - zbiór punktów, których pierwsza współrzędna jest parzysta, druga nieparzysta,
$D$ - zbiór punktów, których pierwsza współrzędna jest nieparzysta, druga parzysta.

Gdy dwa punkty płaszczyzny należą do jednego z tych zbiorów, to mówimy, że mają ten sam typ parzystości. Jeżeli punkty $P = (p_1,p_2)$ i $Q = (q_1, q_2)$ mają ten sam typ parzystości, to środek odcinka $\overline{PQ}$ ma współrzędne
$\left( \displaystyle \frac{1}{2} (p_1+q_1), \frac{1}{2} (p_2+q_2) \right)$ będące liczbami całkowitymi (suma liczb tej samej parzystości jest liczbą parzystą).

Powróćmy do sześciokątów wypukłych, których każdy wierzchołek ma współrzędne całkowite. Wśród sześciu wierzchołków sześciokąta można znaleźć dwa mające ten sam typ parzystości.

Jeśli dwa kolejne wierzchołki (np. $K$ i $L$ ) sześciokąta $KLMNOP$ mają ten sam typ parzystości, to łącząc środek $S$ odcinka $\overline{KL}$ z punktem $M$ otrzymamy sześciokąt $KSMNOP$ mający pole mniejsze od sześciokąta $KLMNOP$ . Przy wyznaczaniu kresu dolnego pól sześciokątów możemy więc ograniczyć się do takich sześciokątów, w których kolejne wierzchołki nie mają tego samego typu parzystości. Wobec tego istnieją pewne dwa niekolejne wierzchołki mające ten sam typ parzystości. Środek odcinka łączącego te wierzchołki ma współrzędne całkowite i leży wewnątrz sześciokąta. Łącząc ten środek z wszystkimi wierzchołkami sześciokąta otrzymamy sześć trójkątów, których suma pól równa jest polu sześciokąta. Wobec tego na mocy lematu pole sześciokąta jest nie mniejsze od $6 \cdot \frac{1}{2} = 3$ . Przykładem sześciokąta wypukłego mającego wierzchołki o współrzędnych całkowitych, którego pole wynosi $3$ , jest sześciokąt o wierzchołkach $K = (- 1, - 1)$ , $L = (0, - 1)$ , $M = (1, 0)$ , $N = (1,1)$ , $O = (0,1)$ , $P = (- 1, 0)$ .

Szukany kres dolny wynosi więc $3$ .

XXXV OM - II - Zadanie 6

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Ciąg $(x_n)$ określony jest wzorami

$ x_1=c,\; x_{n+1} = cx_n + \sqrt{(c^2-1)(x_n^2-1)} \quad\text{ dla }\quad n=1,2,\ldots $

Dowieść, że jeśli $c$ jest liczbą naturalną, to wszystkie liczby $x_n$ są naturalne.

Rozwiązanie

Wyrazy $x_1 = c$ , $x_2 = 2c^2 - 1$ są liczbami naturalnymi.

Załóżmy dla pewnego $n$ , że wszystkie wyrazy $x_k$ przy $k \leq n$ są naturalne. Udowodnimy, że $x_{n+1}$ jest liczbą naturalną. Z danego wzoru wynika, że

$ x_{n+1} -cx_n = \sqrt{(c^2-1)(x_n^2-1)}, $

więc

$ (*) \qquad(x_{n+1}-cx_n^2) =(c^2-1)(x_n^2-1) $

i podobnie

$ (x_n-cx_{n-1})^2 =(c^2-1)(x^2_{n-1}-1). $

Z ostatniej równości otrzymujemy

$ \begin{split} x_n^2 - 2cx_n x_{n-1} + c^2 x^2_{n-1} =c^2 x^2_{n-1} - c^2 - x^2_{n-1}+1,\\ x_n^2 + c^2 - 1 = 2cx_n x_{n-1} - x^2_{n-1}, \end{split} $

a po odjęciu obu stron od $c^2x^2_n$

$ c^2 x_n^2 -x_n^2 - c^2 + 1 = c^2x_n^2 - 2cx_n x_{n-1} + x_{n-1}^2, $

czyli

$ (**)\qquad (c^2-1)(x_n^2-1) = (cx_n - x_{n-1})^2. $

Porównując (*) i (**) stwierdzamy, że

$ (x_{n+1}-cx_n)^2 = (cx_n - x_{n-1})^2. $

Ponieważ ze wzoru określającego ciąg wynika, że $x_{n+1} \geq cx_n$ oraz $cx_n \geq x_{n-1}$ , więc

$ x_{n + 1} - cx_n = cx_n - x_{n-1}, $

a zatem

$ x_{n+1} = 2cx_n - x_{n-1}. $

Na mocy przyjętego założenia indukcyjnego liczby $x_n$ i $x_{n-1}$ są naturalne, więc liczba $2cx_n - x_{n-1}$ jest całkowita. Jest to ponadto liczba dodatnia, a więc $x_{n+ 1}$ jest liczbą naturalną.

Na mocy zasady indukcji wszystkie wyrazy ciągu $(x_n)$ są liczbami naturalnymi.