LI OM

LI Olimpiada Matematyczna

LI OM - I etap

I etap LI Olimpiady Matematycznej

Załącznik	Wielkość
LI OM I etap - Zadania [1]	71.5 KB
LI OM I etap - Zadania z rozwiązaniami [2]	180.82 KB

LI OM - I - Zadanie 1

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Dana jest liczba naturalna $n \geq 3$ . Udowodnić, ze suma sześcianów wszystkich liczb naturalnych mniejszych od $n$ , względnie pierwszych z $n$ , dzieli się przez $n$ .

Rozwiązanie

Każda liczba naturalna mniejsza od $n$ i względnie pierwsza z $n$ jest równa $k$ lub $n-k$ , gdzie $k$ jest pewną liczbą naturalną mniejszą od $n/2$ i względnie pierwszą z $n$ . Zatem dana w zadaniu suma sześcianów jest równa

$ \sum_{{1\leq k<n/2} \atop {(k,n)=1}} k^3+(n-k)^3 = \sum_{{1\leq k<n/2}\atop {(k,n)=1}}n^{3}-3kn^{2}+3k^{2}n=n\cdot\sum_{{1\leq k<n/2} \atop {(k,n)=1}}n^{2}-3kn+3k^{2}, $

a więc jest podzielna przez $n$ .

LI OM - I - Zadanie 2

Zawody matematyczne:

LI OM, 1999-2000

Etap:

W trójkącie ostrokątnym $ABC$ spełniony jest warunek

$ \measuredangle ACB=2 \measuredangle ABC. $

Punkt $D$ leży na boku $BC$ , przy czym $\measuredangle BAD =\frac{1}{2} \measuredangle ABC$ . Dowieść, że

$ (1)\qquad\frac{1}{BD}=\frac{1}{AB}+\frac{1}{AC}. $

Rozwiązanie

Wykażemy, że równość (1) jest prawdziwa dla dowolnego trójkąta ABC, niekoniecznie ostrokątnego.

Niech $E$ będzie takim punktem półprostej $BC^\to$ , że $AD$ jest dwusieczną kąta $BAE$ (rys. 1 i 2).

Wówczas $\measuredangle EBA =\measuredangle EAB$ . Jeżeli punkt $E$ leży na boku $BC$ (rys. 1), to

$ \measuredangle AEC= 2\measuredangle ABC = \measuredangle ACE. $

Jeśli natomiast punkt $E$ nie leży na boku $BC$ (rys. 2), to

$ \measuredangle AEC= 180^\circ - 2\measuredangle ABE = 180^\circ - \measuredangle ACB = \measuredangle ACE. $

Zatem w obu przypadkach $BE = AE = AC$ . Na mocy twierdzenia o dwusiecznej otrzymujemy

$ \frac{BD}{AB} + \frac{BD}{AC} = \frac{DE}{AE} + \frac{BD}{AE}=\frac{BE}{AE}=1, $

co należało udowodnić.

LI OM - I - Zadanie 3

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Suma liczb dodatnich $a$ , $b$ , $c$ równa jest $1$ . Udowodnić, że

$ a^2 + b^2 + c^2 + 2\sqrt{3abc} \leq 1 . $

Rozwiązanie

Wystarczy dowieść, że dla dowolnych liczb dodatnich $a$ , $b$ , $c$ zachodzi nierówność

$ a^2 + b^2 + c^2 + 2\sqrt{3abc(a + b + c)} \leq (a + b + c)^2. $

Przekształcając równoważnie powyższą zależność otrzymujemy

$ \sqrt{3abc(a+b+c)} \leq ab + bc + ca. $

Wykonując podstawienie $x = bc$ , $y = ca$ , $z = ab$ , sprowadzamy dowodzoną nierówność do postaci

$ \sqrt{3(xy+yz + zx)} = x+y + z. $

Podnosząc do kwadratu obie strony ostatniej nierówności i przekształcając równoważnie otrzymujemy

$ xy+yz + xz=x^2 + y^2 + z^2 \ \textrm{lub}\ (x-y)^2 + (y-z)^2 + (z-x)^2\geq 0, $

co jest prawdą.

LI OM - I - Zadanie 4

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Każdy punkt okręgu jest pomalowany jednym z trzech kolorów. Dowieść, że pewne trzy punkty jednego koloru są wierzchołkami trójkąta równoramiennego.

Rozwiązanie

Niech $A_1,A_2,\ldots ,A_{13}$ będą wierzchołkami dowolnego $13$ -kąta foremnego wpisanego w dany okrąg. Wykażemy, że wśród dowolnych pięciu wierzchołków tego $13$ -kąta znajdą się trzy będące wierzchołkami trójkąta równoramiennego. Ponieważ wśród dowolnych trzynastu punktów danego okręgu zawsze znajdzie się pięć pomalowanych tym samym kolorem, zadanie zostanie rozwiązane.

Przypuśćmy więc, że udało się tak wybrać pięć wierzchołków spośród $A_1,A_2,\ldots ,A_{13}$ , że żadne trzy spośród wybranych punktów nie tworzą trójkąta równoramiennego.

Załóżmy najpierw, że wśród wybranych punktów nie ma dwóch sąsiednich wierzchołków $13$ -kąta $A_1 A_2 \ldots A_{13}$ . Wówczas wśród wybranych punktów znajdziemy dwa oddzielone dokładnie jednym wierzchołkiem, który nie został wybrany. Bez szkody dla ogólności rozumowania, możemy przyjąć, że są to $A_1$ i $A_3$ . Ponieważ żadne trzy wybrane wierzchołki nie tworzą trójkąta równoramiennego, więc nie został wybrany żaden z punktów: $A_{12}$ , $A_{13}$ , $A_2$ , $A_4$ , $A_5$ (rys. 1).

Ponieważ trójkąt $A_1A_6A_{11}$ jest równoramienny, więc co najmniej jeden z wierzchołków $A_6$ , $A_{11}$ nie został wybrany. Bez straty ogólności rozumowania możemy przyjąć, że tym wierzchołkiem jest $A_6$ . Zatem spośród pięciu punktów $A_7$ , $A_8$ , $A_9$ , $A_{10}$ , $A_{11}$ dokładnie trzy zostały wybrane, przy czym żadne dwa z nich nie są kolejnymi wierzchołkami $13$ -kąta $A_1A_2\ldots A_{13}$ . Musiały więc zostać wybrane punkty $A_7$ , $A_9$ , $A_{11}$ . To jednak nie jest możliwe, gdyż punkty te tworzą trójkąt równoramienny (rys. 2). Otrzymaliśmy sprzeczność.

Pozostał do rozpatrzenia przypadek, w którym wśród wybranych wierzchołków znajdują się dwa sąsiednie, powiedzmy $A_1$ i $A_2$ . Oznacza to, że nie został wybrany żaden z wierzchołków: $A_{13}$ , $A_3$ , $A_8$ (rys. 3).

Ponieważ trójkąty $A_2A_4A_6$ , $A_1A_6A_{11}$ , $A_{11} A_1 A_4$ są równoramienne, więc został wybrany co najwyżej jeden z punktów: $A_4$ , $A_6$ , $A_{11}$ . Analogicznie stwierdzamy, że został wybrany co najwyżej jeden z punktów: $A_5$ , $A_{10}$ , $A_{12}$ . Zatem wybrany być musiał co najmniej jeden z punktów $A_7$ , $A_9$ . Bez straty ogólności przyjmijmy, że został wybrany punkt $A_7$ (rys. 4). Równoramienność trójkątów: $A_1A_4A_7$ , $A_2A_{10}A_7$ , $A_2A_{11}A_7$ oraz $A_2A_{12}A_7$ dowodzi, że nie wybrano punktów: $A_4$ , $A_{10}$ , $A_{11}$ oraz $A_{12}$ .

Zatem wśród wybranych pięciu punktów muszą być dwa spośród $A_5$ , $A_6$ , $A_9$ . Z uwagi na równoramienność trójkąta $A_5A_6A_7$ wybrany mógł być tylko jeden z punktów $A_5$ , $A_6$ . Zatem wybranym punktem jest $A_9$ (rys. 5). To z kolei oznacza, że nie został wybrany punkt $A_5$ , gdyż trójkąt $A_5A_7A_9$ jest równoramienny.

Tak więc piątym z wybranych punktów musi być $A_6$ , co daje sprzeczność, gdyż trójkąt $A_9A_1A_6$ jest równoramienny (rys. 6).

Tym samym wykazaliśmy, że wybór pięciu wierzchołków $13$ -kąta, z których żadne trzy nie wyznaczają trójkąta równoramiennego, nie jest możliwy, co kończy rozwiązanie zadania.

LI OM - I - Zadanie 5

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Wyznaczyć wszystkie pary $(a,b)$ liczb naturalnych, dla których liczby $a^3 + 6ab + 1$ i $b^3 + 6ab + 1$ są sześcianami liczb naturalnych.

Rozwiązanie

Niech $a$ i $b$ będą liczbami spełniającymi warunki zadania. Bez szkody dla ogólności rozumowania możemy założyć, że $a \leq b$ . Wówczas

$ b^3 < b^3 + 6ab+ 1 \leq b^3 + 6b^2 + 1< b^3 + 6b^2 + 12b + 8 = (b + 2)^3 . $

Skoro liczba $b^3+6ab + 1$ jest sześcianem liczby całkowitej, to musi zachodzić równość

$ (1)\qquad b^3+ 6ab +1 = (b+1)^3. $

Przekształcając równoważnie powyższy związek otrzymujemy po kolei

$ (2)\qquad \begin{split} b^{3}+6ab+1&=b^{3}+3b^{2}+3b+1\\ 2ab&=b(b+1)\\ b&=2a-1 \end{split} $

Pozostaje rozstrzygnąć, dla jakich par $(a, b)$ spełniających warunek (2) liczba

$ a^3 +6ab+1 $

jest sześcianem liczby całkowitej. Na mocy zależności (2) powyższa liczba jest równa $a^3 + 12a^2 - 6a + 1$ . Z nierówności

$ a^3 \leq a^3 + 6a^2-6a < a^3+12a^2-6a + 1< a^3 + 12a^2 + 48a + 64 = (a + 4)^3 $

wynika, że jeżeli liczba $a^3 + 12a^2 - 6a+ 1$ jest sześcianem liczby całkowitej, to jest ona równa $(a+ 1)^3$ , $(a + 2)^3$ lub $(a + 3)^3$ . Należy więc rozważyć trzy przypadki:

(a) $a^3 + 12a^2 - 6a + 1 = (a +1)^3$

Wówczas otrzymujemy $9a^{2}-9a=0$ , skąd $a = 0$ lub $a = 1$ .

(b) $a^{3}+12a^{2}-6a+1=(a+2)^{3}$

Stąd mamy $6a^2 - 18a - 7 = 0$ . Uzyskane równanie nie ma rozwiązań w liczbach całkowitych, gdyż lewa strona nie jest podzielna przez $3$ , a prawa jest.

Wtedy uzyskujemy $3a^2 - 33a - 26 = 0$ . Podobnie jak w przypadku (b), otrzymane równanie nie ma rozwiązań w liczbach całkowitych, gdyż lewa strona nie jest podzielna przez $3$ , a prawa jest równa $0$ .

Ostatecznie znaleźliśmy tylko jedną parę $(a,b) = (1,1)$ spełniającą warunki zadania.

LI OM - I - Zadanie 6

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Punkt $X$ leży wewnątrz lub na brzegu trójkąta $ABC$ , w którym kąt $C$ jest prosty. Punkty $P$ , $Q$ i $R$ są odpowiednio rzutami punktu $X$ na boki $BC$ , $CA$ i $AB$ . Udowodnić, ze równość

$ AR \cdot RB = BP \cdot PC + AQ \cdot QC $

zachodzi wtedy i tylko wtedy, gdy punkt $X$ leży na boku $AB$ .

Rozwiązanie

Wprowadźmy dla zwięzłości zapisu następujące oznaczenie:

$ w = 2 \cdot (AR\cdot RB - BP\cdot PC - AQ \cdot QC). $

Należy wykazać, ze $w = 0$ wtedy i tylko wtedy, gdy $XR = 0$ .

Na mocy twierdzenia Pitagorasa otrzymujemy zależność (rys. 1):

$ (AR + RB)^2 = (AQ+QC)^2 + (CP+PB)^2. $

Przekształcając równoważnie powyższą równość uzyskujemy po kolei:

$ \begin{split} &w = AQ^2 +QC^2+ CP^2+ PB^2- AR^2- RB^2 \\ &w = AQ^2 +PX^2+ QX^2+ PB^2- AR^2- RB^2 \\ &w = AX^2 +BX^2- AR^2- RB^2 \\ &w = 2XR^2 \end{split} $

Z ostatniej równości wynika natychmiast, ze $w = 0$ wtedy i tylko wtedy, gdy $XR= 0$ .

LI OM - I - Zadanie 7

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Wykazać, że dla dowolnej liczby całkowitej dodatniej $n$ i dowolnej liczby $t\in(\frac{1}{2},1)$ istnieją takie liczby $a,b \in (1999,2000)$ , że

$ \frac{1}{2}a^{n}+\frac{1}{2}b^{n}<(ta+(1-t)b)^{n}. $

Rozwiązanie

Niech $c = 3999/2$ . Liczb $a$ , $b$ szukamy w postaci $a = c+x$ , $b = c-x$ , gdzie $x \in (0, \frac{1}{2})$ . Wówczas

$ \begin{split} (ta+(1-t)b)^{n}&- \frac{1}{2}a^{n}-\frac{1}{2}b^{n}=\\ &=(ct+tx+(1-t)c-(1-t)x)^{n}-\frac{1}{2}(c+x)^{n}-\frac{1}{2}(c-x)^{n}=\\ &=(c+(2t-1)x)^{n}-\frac{1}{2}(c+x)^{n}-\frac{1}{2}(c-x)^{n}=\\ &=(c+sx)^{n}-\frac{1}{2}(c+x)^{n}-\frac{1}{2}(c-x)^{n},\\ \end{split} $

gdzie $s = 2t - 1 > 0$ . Po rozpisaniu ze wzoru dwumianowego Newtona ostatnie wyrażenie przyjmuje postać

$ (1) \qquad w(x) = sx + x^2p(x) , $

gdzie $p(x)$ jest pewnym wielomianem.

Chcemy wykazać, że dla pewnej liczby $y \in (0,\frac{1}{2})$ , liczba $w(y)$ jest dodatnia. Z równości (1) wynika, że

$ \lim_{x\to 0} \frac{w(x)}{x}=s>0. $

Zatem istnieje taka liczba $y \in (0,\frac{1}{2})$ , że wyrażenie $w(y)/y$ , a co za tym idzie również wyrażenie $w(y)$ , ma wartość dodatnią. To zaś kończy dowód.

LI OM - I - Zadanie 8

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Liczby $c(n,k)$ są określone dla liczb całkowitych nieujemnych $n\geq k$ w ten sposób, że zachodzą równości:

$ c(n,0) = c(n,n) = 1\ \textrm{dla każdej liczby}\ n \geq 0, $

$ c(n+1,k) = 2^kc(n,k) + c(n,k-1)\ \textrm{dla}\ n\geq k \geq 1. $

Dowieść, że $c(n,k) = c(n,n-k)$ dla $n\geq k \geq 0$ .

Rozwiązanie

Niech $f$ będzie funkcją określoną na zbiorze liczb całkowitych nieujemnych zdefiniowaną wzorami:

$ f(0) = 1,\ f(m) = (2^1-1)(2^2-1)\cdots(2^m - 1)\ \textrm{dla}\ m\geq 1. $

Niech ponadto

$ a(n,k)=\frac{f(n)}{f(k)f(n-k)}\ \textrm{dla}\ n\geq k\geq 0. $

Wówczas $a(n,k) = a(n,n-k)$ . Wykażemy, że $a(n,k) = c(n,k)$ .

Ponieważ warunki dane w treści zadania wyznaczają jednoznacznie liczby $c(n,k)$ , więc wystarczy dowieść, że liczby $a(n,k)$ spełniają te same warunki.

Oczywiście $a(n,0) = a(n,n) = 1$ . Ponadto

$ \begin{split} 2^{k}a(n,k)+a(n,k-1)=\frac{2^{k}f(n)}{f(k)f(n-k)}+\frac{f(n)}{f(k-1)f(n-k+1)}=\qquad&\\ \begin{split} &=\frac{2^{k}f(n)(2^{n-k+1}-1)}{f(k)f(n-k)(2^{n-k+1}-1)}+\frac{f(n)(2^{k}-1)}{f(k-1)(2^{k}-1)f(n-k+1)}=\\ &=f(n)\cdot\frac{2^{k}(2^{n-k+1}-1)+(2^{k}-1)}{f(k)f(n-k+1)}=\\ &=f(n)\cdot\frac{2^{n+1}-1}{f(k)f(n+1-k)}=\frac{f(n+1)}{f(k)f(n+1-k)}=a(n+1,k), \end{split}& \end{split} $

co dowodzi, że $a(n,k) = c(n,k)$ .

LI OM - I - Zadanie 9

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Dane są takie liczby całkowite dodatnie $m$ i $n$ , że $mn | m^2 + n^2 + m$ . Wykazać, że $m$ jest kwadratem liczby całkowitej.

Rozwiązanie

Z drugiej strony, $m | m^2 + n^2 + m$ , skąd uzyskujemy podzielność $m|n^2$ . Zatem $m$ jest wspólnym dzielnikiem liczb $n^2$ i $m^2$ . To oznacza, że największy wspólny dzielnik liczb $m^2$ i $n^2$ , który jest równy $d^2$ , jest podzielny przez $m$ . Wobec wyżej udowodnionej podzielności $d^2 | m$ otrzymujemy $m = d^2$ .

LI OM - I - Zadanie 10

Zawody matematyczne:

LI OM, 1999-2000

Etap:

W przestrzeni dane są trzy wzajemnie prostopadłe wektory jednostkowe $\overrightarrow{OA}$ , $\overrightarrow{OB}$ , $\overrightarrow{OC}$ . Niech $\omega$ będzie płaszczyzną przechodzącą przez punkt $O$ , zaś $A'$ , $B'$ , $C'$ - rzutami punktów $A$ , $B$ , $C$ odpowiednio na płaszczyznę $\omega$ . Wyznaczyć zbiór wartości wyrażenia

$ (1) \quad (OA')^2 + (OB')^2 + (OC')^2 $

dla wszystkich płaszczyzn $\omega$ .

Rozwiązanie

Wykażemy, że wartość wyrażenia (1) jest równa $2$ , niezależnie od wyboru płaszczyzny $\omega$ .

Niech $\omega$ będzie dowolną płaszczyzną przechodzącą przez punkt $O$ , zaś $\pi$ płaszczyzną zawierającą punkty $O$ , $A$ , $B$ . Oznaczmy przez $\ell$ wspólną prostą płaszczyzn $\pi$ i $\omega$ . Niech $X$ , $Y$ będą rzutami prostokątnymi odpowiednio punktów $A$ , $B$ na prostą $\ell$ . Wówczas, niezależnie od położenia punktów $A$ , $B$ względem prostej $\ell$ (rys. 1 i 2),

$ \measuredangle OAX = 90^\circ - \measuredangle AOX = \measuredangle BOY = \alpha. $

Stąd

$ (2) \qquad AX^2 + BY^2 = \cos^2 a + \sin^2 a = 1. $

Ponadto $\measuredangle AXA' = \measuredangle BYB'$ = (kąt pomiędzy płaszczyznami $\pi$ i $\omega$ ) = $\beta$ . Zatem na mocy równości (2),

$ (AA')^2 + (BB')^2 = AX^2 sin^2\beta + BY^2\sin^2\beta = \sin^2\beta. $

Na mocy twierdzenia Pitagorasa oraz powyższej równości otrzymujemy

$ (3)\qquad (OA')^2 + (OB')^2 = 2 - (AA')^2 - (BB')^2 = 2 - \sin^2\beta. $

Wektor $\overrightarrow{OC}$ jest prostopadły do płaszczyzny $\pi$ , skąd $\measuredangle COC' = 90^\circ - \beta$ . Zatem

$ (4)\qquad (OC')^2 = \cos^2(90^\circ - \alpha) = \sin^2 \beta . $

Dodając stronami równości (3) i (4) uzyskujemy

$ (OA')^2 + (OB')^2 + (OC')^2 = 2, $

niezależnie od wyboru płaszczyzny $\omega$ .

LI OM - I - Zadanie 11

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Dana jest liczba całkowita dodatnia $n$ oraz zbiór $M$ , złożony z $n^2 + 1$ różnych liczb całkowitych dodatnich i mający następującą własność: wśród $n+1$ liczb dowolnie wybranych ze zbioru $M$ znajduje się para liczb, z których jedna dzieli się przez drugą. Udowodnić, że w zbiorze $M$ istnieją różne liczby $a_1,a_2,\ldots,a_{n+1}$ spełniające warunek: dla $i = 1,2,\ldots,n$ liczba $a_i$ dzieli się przez $a_{i+1}$ .

Rozwiązanie

Niech $k \in M$ . Oznaczmy przez $d(k)$ największą liczbę naturalną $\ell$ , dla której istnieją różne liczby $a_1 = k, a_2, a_3, \ldots, a_\ell$ spełniające warunek: dla $i = 1,2,\ldots,\ell-1$ liczba $a_i$ dzieli się przez $a_{i+1}$ .

Przypuśćmy, że teza zadania nie jest spełniona. To oznacza, że dla dowolnego $k \in M$ mamy $1 \leq d(k) \leq n$ . Wówczas na mocy zasady szufladkowej, istnieją takie różne liczby $k_1,k_2,\ldots,k_{n+1}$ , że

$ d(k_1) = d(k_2) = \ldots = d(k_{n+1}) = m. $

Z założeń zadania wynika, że dla pewnych różnych liczb $s$ , $t$ zachodzi podzielność $k_s|k_t$ . Warunek $d(k_s) = m$ oznacza, że istnieją liczby $a_1 = k_s, a_2, \ldots, a_m$ , spełniające: dla $i = 1,2,\ldots,m-1$ liczba $a_i$ dzieli się przez $a_{i+1}$ . Jednak wtedy liczby $b_1 = k_t, b_2 =a_1 = k_s , b_3 = a_2, \ldots , b_{m+1} =a_m$ spełniają warunek: dla $i = 1,2,\ldots,m$ liczba $b_i$ dzieli się przez $b_{i+1}$ . To dowodzi, że $d(k_t) \geq m + 1$ wbrew założeniu, że $d(k_t) = m$ .

Otrzymaliśmy sprzeczność.

LI OM - I - Zadanie 12

Zawody matematyczne:

LI OM, 1999-2000

Etap:

W trójkącie ostrokątnym $ABC$ punkty $D$ , $E$ , $F$ leżą odpowiednio na bokach $BC$ , $CA$ , $AB$ . Okręgi opisane na trójkątach $AEF$ , $BFD$ , $CDE$ przecinają się w punkcie $P$ . Udowodnić, że jeżeli

$ \frac{PD}{PE} = \frac{BD}{AE},\ \frac{PE}{PF} = \frac{CE}{BF},\ \frac{PF}{PD} = \frac{AF}{CD}, $

to $AD$ , $BE$ , $CF$ są wysokościami trójkąta $ABC$ .

Rozwiązanie

Wykorzystamy następujące

Twierdzenie

Wysokości $AD$ , $BE$ , $CF$ trójkąta $ABC$ przecinają się w punkcie $H$ . Punkty $K$ , $L$ , $M$ są odpowiednio środkami boków $BC$ , $CA$ , $AB$ . Punkty $X$ , $Y$ , $Z$ są odpowiednio środkami odcinków $AH$ , $BH$ , $CH$ . Wówczas następujące punkty: $D$ , $E$ , $F$ , $K$ , $L$ , $M$ , $X$ , $Y$ , $Z$ leżą na jednym okręgu (rys. 1).

Okrąg ten nazywa się okręgiem dziewięciu punktów trójkąta $ABC$ .

Z powyższego twierdzenia wynika, że jeśli okrąg przechodzący przez środki boków trójkąta ostrokątnego $ABC$ przecina obwód tego trójkąta po raz drugi w punktach $D$ , $E$ , $F$ , to punkty $D$ , $E$ , $F$ są spodkami wysokości trójkąta $ABC$ .

Przystępujemy do rozwiązania zadania.

Na półprostej $FA^\to$ odkładamy taki punkt $Q$ , aby zachodziła następująca równość kątów: $\measuredangle FPQ = \measuredangle EPC$ (rys. 2).

Punkty $A$ , $E$ , $P$ , $F$ leżą na jednym okręgu, więc $\measuredangle QFP = \measuredangle CEP$ . Z powyższych równości wynika, że trójkąty $PQF$ oraz $PCE$ są podobne. Zatem

$ \frac{PF}{PE}=\frac{PQ}{PC}. $

Ponadto $\measuredangle FPE = \measuredangle QPC$ . Z dwóch ostatnich równości wynika, że trójkąty $PFE$ oraz $PQC$ są podobne. Z zależności w treści zadania oraz z podobieństwa trójkątów $PQF$ , $PCE$ otrzymujemy

$ \frac{BF}{CE}=\frac{PF}{PE}=\frac{QF}{CE}, $

skąd $BF = QF$ . Zatem punkt $F$ jest środkiem odcinka $BQ$ .

Niech $K$ będzie środkiem boku $BC$ . Wówczas proste $KF$ oraz $CQ$ są równoległe. Zatem kąt $EFK$ jest równy kątowi pomiędzy prostymi $FE$ oraz $CQ$ . Natomiast na mocy podobieństwa trójkątów $PFE$ oraz $PQC$ , kąt pomiędzy prostymi $FE$ oraz $CQ$ jest równy kątowi pomiędzy odcinkami $PE$ i $PC$ , czyli kątowi $EPC$ . Punkty $E$ , $P$ , $D$ , $C$ leżą na jednym okręgu, skąd wynika równość $\measuredangle EPC = \measuredangle EDC$ .

Z powyższych rozważań uzyskujemy zależność $\measuredangle EFK = \measuredangle EDC$ . Dowodzi ona, że punkty $D$ , $K$ , $E$ , $F$ leżą na jednym okręgu, niezależnie od tego, z której strony punktu $K$ leży punkt $D$ . Jeżeli $K = D$ , to okrąg opisany na trójkącie $DEF$ jest styczny do prostej $BC$ w punkcie $D$ .

Innymi słowy: okrąg opisany na trójkącie $DEF$ przechodzi przez punkt $D$ oraz środek boku $BC$ i nigdzie indziej nie przecina prostej $BC$ . Analogicznie dowodzimy, że ten sam okrąg przechodzi przez środki pozostałych boków. Poza punktami $D$ , $E$ , $F$ oraz środkami boków trójkąta $ABC$ okrąg ten nie ma punktów wspólnych z obwodem trójkąta $ABC$ .

Wykazaliśmy więc, że okrąg przechodzący przez środki boków trójkąta $ABC$ przecina jego obwód po raz drugi w punktach $D$ , $E$ , $F$ . To zaś dowodzi, że proste $AD$ , $BE$ , $CF$ są wysokościami trójkąta $ABC$ .

LI OM - II etap

II etap LI Olimpiady Matematycznej

Załącznik	Wielkość
LI OM II etap - Zadania z rozwiązaniami [3]	219.04 KB

LI OM - II - Zadanie 1

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Rozstrzygnąć, czy każdą liczbę wymierną dodatnią można przedstawić w postaci

$ \frac{a^2+b^3}{c^5+d^7}, $

gdzie $a$ , $b$ , $c$ , $d$ są liczbami całkowitymi dodatnimi.

Rozwiązanie

Dla dowolnych liczb całkowitych dodatnich $p$ , $q$ zachodzą następujące równości:

$ \frac{p}{q}=\frac{p}{q}\cdot\frac{p^{5}q^{4}+p^{14}q^{6}}{p^{5}q^{4}+p^{14}q^{6}}=\frac{p^{6}q^{4}+p^{15}q^{6}}{p^{5}q^{5}+p^{14}q^{7}}=\frac{(p^{3}q^{2})^{2}+(p^{5}q^{2})^{3}}{(pq)^{5}+(p^{2}q)^{7}}. $

Zatem każdą liczbę wymierną dodatnią można przedstawić w żądanej postaci.

LI OM - II - Zadanie 2

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Dwusieczna kąta $BAC$ trójkąta $ABC$ przecina okrąg opisany na tym trójkącie w punkcie $D$ różnym od $A$ . Punkty $K$ i $L$ są rzutami prostokątnymi odpowiednio punktów $B$ i $C$ na prostą $AD$ . Dowieść, że

$ AD \geq BK + CL. $

Rozwiązanie

Oznaczmy przez $o$ okrąg opisany na trójkącie $ABC$ . Z równości kątów $BAD$ i $DAC$ wynika, że długości łuków $BD$ i $DC$ okręgu $o$ są równe (długość łuku $XY$ jest mierzona od punktu $X$ do punktu $Y$ w kierunku przeciwnym do ruchu wskazówek zegara).

Niech $E$ będzie punktem symetrycznym do punktu $D$ względem symetralnej boku $AB$ , zaś niech $N$ będzie rzutem prostokątnym punktu $E$ na prostą $AD$ (rys. 1 i 2). Wówczas $AD = BE$ . Ponadto długości łuków $DC$ i $EA$ są równe, co oznacza, że $EN = CL$ .

Punkty $B$ i $E$ leżą po dwóch różnych stronach prostej $AD$ . Zatem długość odcinka $BE$ jest nie mniejsza niż suma odległości punktów $B$ i $E$ od prostej $AD$ . Innymi słowy $BE\geq BK + EN$ , czyli $AD \geq BK + CL$ .

LI OM - II - Zadanie 3

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Na polach szachownicy $n \times n$ rozmieszczono $n^2$ różnych liczb całkowitych, po jednej na każdym polu. W każdej kolumnie pole z największą liczbą pomalowano na czerwono. Zbiór $n$ pól szachownicy nazwiemy dopuszczalnym, jeżeli żadne dwa z tych pól nie znajdują się w tym samym wierszu, ani w tej samej kolumnie. Spośród wszystkich zbiorów dopuszczalnych wybrano zbiór, dla którego suma liczb umieszczonych na jego polach jest największa.

Wykazać, że w tak wybranym zbiorze jest czerwone pole.

Rozwiązanie

Przeprowadzimy dowód nie wprost.

Załóżmy, że w wybranym zbiorze dopuszczalnym (oznaczmy go przez $A$ ) nie ma czerwonego pola.

Zdefiniujemy ciąg pól $D_1,E_1,D_2,E_2,\ldots$ danej szachownicy według niżej opisanej reguły. (Dla $n = 8$ proces wyboru pól $D_1,E_1,D_2,E_2,\ldots$ jest przedstawiony na rysunkach 1 i 2. Pola czerwone są zacieniowane, zaś pola ze zbioru $A$ są oznaczone kółkiem.)

Pole $D_1$ jest dowolnym polem ze zbioru $A$ . Niech $E_1$ będzie polem czerwonym leżącym w tej samej kolumnie, co $D_1$ .

Następnie rozważamy to pole $D_2$ ze zbioru $A$ , które leży w tym samym wierszu, co $E_1$ . Przez $E_2$ oznaczamy pole czerwone leżące w tej samej kolumnie, co $D_2$ . Postępowanie to kontynuujemy. (Ogólnie: pole czerwone $E_i$ leży w tej samej kolumnie, co $D_i$ , natomiast pole $D_{i+1}$ jest polem ze zbioru $A$ leżącym w tym samym wierszu, co $E_i$ .)

W ten sposób otrzymujemy ciąg pól $D_1,E_1,D_2,E_2,D_3,\ldots$ , w którym każde pole jednoznacznie wyznacza pole następne. Ponieważ pól czerwonych jest skończenie wiele, więc znajdziemy takie liczby całkowite dodatnie $i$ , $t$ , dla których $E_i = E_{i+t}$ oraz $E_i \neq E_{i+s}$ dla $s= 1, 2, \ldots, t-1$ . (W naszym przykładzie przedstawionym na rysunkach 1 i 2, $E_2 = E_5$ , a więc $i = 2$ , $t = 3$ .)

Usuwamy ze zbioru $A$ pola $D_{i+1},D_{i+2},\ldots,D_{i+t}$ zastępując je odpowiednio polami $E_{i+1},E_{i+2},\ldots,E_{i+t}$ (rys. 3). Otrzymany w ten sposób zbiór oznaczmy przez $B$ .

Z określenia ciągu $D_1,E_1,D_2,E_2,D_3,\ldots$ wynika, że pola

$ D_{i+1},D_{i+2},\ldots,D_{i+t} $

znajdują się odpowiednio w tych samych kolumnach, co pola

$ E_{i+1},E_{i+2},\ldots,E_{i+t} $

oraz odpowiednio w tych samych wierszach, co pola

$ E_i = E_{i+t}, E_{i+1}, E_{i+2}, \ldots, E_{i+t-1} . $

Zatem zbiór $B$ jest dopuszczalny. Ponadto liczby, które zostały napisane na polach $E_{i+1},E_{i+2},\ldots,E_{i+t}$ są większe odpowiednio od liczb napisanych na polach $D_{i+1},D_{i+2},\ldots,D_{i+t}$ . Wynika stąd, że suma liczb napisanych na polach zbioru $B$ jest większa od sumy liczb napisanych na polach zbioru $A$ . To jednak przeczy założeniu, że $A$ ma największą sumę liczb spośród wszystkich zbiorów dopuszczalnych.

LI OM - II - Zadanie 4

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Punkt $I$ jest środkiem okręgu wpisanego w trójkąt $ABC$ , w którym $AB \neq AC$ . Proste $BI$ i $CI$ przecinają boki $AC$ i $AB$ odpowiednio w punktach $D$ i $E$ . Wyznaczyć wszystkie miary kąta $BAC$ , dla których może zachodzić równość $DI = EI$ .

Rozwiązanie

Wykażemy, że jedyną wartością przyjmowaną przez kąt $BAC$ jest $60^\circ$ .

Na mocy twierdzenia sinusów zastosowanego do trójkątów $ADI$ i $AEI$ otrzymujemy $\sin \measuredangle AEI = \sin \measuredangle ADI$ . Stąd

$ \measuredangle AEI = \measuredangle ADI \quad \textrm{lub} \quad \measuredangle AEI+ \measuredangle ADI = 180^\circ. $

Przypuśćmy najpierw, że zachodzi równość $\measuredangle AEI = \measuredangle ADI$ (rys. 1). Wtedy również $\measuredangle AIE = \measuredangle AID$ , co oznacza, że trójkąty $AEI$ oraz $ADI$ są przystające (cecha kąt-bok-kąt). Zatem $AD = AE$ . To dowodzi, że przystające są także trójkąty $ADB$ i $AEC$ (cecha kąt-bok-kąt). Stąd uzyskujemy równość $AB = AC$ , co przeczy założeniom poczynionym w treści zadania.

Pozostał do rozpatrzenia przypadek, w którym $\measuredangle AEI+ \measuredangle ADI = 180^\circ$ (rys. 2). Wtedy punkty $A$ , $E$ , $I$ , $D$ leżą na jednym okręgu. Zatem

$ \measuredangle BAC = \measuredangle DIC = \measuredangle IBC+ \measuredangle ICB = \frac{1}{2} \measuredangle ABC+ \frac{1}{2} \measuredangle BCA. $

Stąd otrzymujemy

$ 180^\circ = \measuredangle BAC + \measuredangle ABC + \measuredangle BCA= \measuredangle BAC + 2\measuredangle BAC = 3 \measuredangle BAC, $

czyli $\measuredangle BAC = 60^\circ$ .

Do zakończenia rozwiązania pozostało wykazać, że istnieje trójkąt $ABC$ , w którym $AB\neq AC$ , $\measuredangle BAC = 60^\circ$ oraz $DI = EI$ . Wykażemy więcej: w każdym trójkącie $ABC$ o kącie $BAC$ równym $60^\circ$ zachodzi równość $DI = EI$ .

Jeżeli $\measuredangle BAC = 60^\circ$ , to

$ \measuredangle DIC =\frac{1}{2} \measuredangle ABC + \frac{1}{2} \measuredangle BCA = 90^\circ - \frac{1}{2} \measuredangle BAC = 60^\circ = \measuredangle BAC. $

Na czworokącie $AEID$ można więc opisać okrąg. Ponieważ $AI$ jest dwusieczną kąta $EAD$ , więc $DI = EI$ .

LI OM - II - Zadanie 5

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Niech $\mathbb{N}$ oznacza zbiór liczb całkowitych dodatnich. Rozstrzygnąć, czy istnieje taka funkcja $f: \mathbb{N}\to \mathbb{N}$ , że dla każdego $n\in \mathbb{N}$ zachodzi równość $f(f(n)) =2n$ .

Rozwiązanie

Taka funkcja istnieje. Oto przykład.

Niech $A$ będzie zbiorem tych liczb całkowitych dodatnich, w których rozkładzie na czynniki pierwsze „trójka" występuje nieparzystą liczbę razy. Funkcję $f$ definiujemy wzorem:

$ f(n)=\left\{\begin{array}{ll} \frac{1}{3}n&\textrm{dla}\quad n\in A,\\ 6n&\textrm{dla}\quad n\in \mathbb{N}\setminus A. \end{array}\right. $

Wówczas, jeśli $n \in A$ , to $f(n) \in \mathbb{N}\setminus A$ , skąd

$ f(f(n)) = f(\frac{1}{3}n) = 2n\ \textrm{dla}\ n\in A. $

Podobnie, jeżeli $n \in \mathbb{N}\setminus A$ , to $f(n) \in A$ , co daje

$ f(f(n)) = f(6n) = 2n \quad \textrm{dla}\ n \in \mathbb{N}\setminus A. $

LI OM - II - Zadanie 6

Zawody matematyczne:

LI OM, 1999-2000

Etap:

Wielomian $w(x)$ stopnia drugiego o współczynnikach całkowitych przyjmuje dla całkowitych $x$ wartości będące kwadratami liczb całkowitych. Dowieść, że wielomian $w(x)$ jest kwadratem pewnego wielomianu.

Rozwiązanie

Niech $w(x) = ax^2 + bx + c$ . Wprowadźmy oznaczenie: $k_n = \sqrt{w(n)}$ dla dowolnej liczby całkowitej dodatniej $n$ . Wówczas $k_n$ może być zerem dla co najwyżej dwóch wartości $n$ . Dla pozostałych $n$ mamy

$ k_{n+1}-k_{n}=\frac{k_{n+1}^{2}-k_{n}^{2}}{k_{n+1}+k_{n}}=\frac{(2n+1)a+b}{\sqrt{a(n+1)^{2}+b(n+1)+c}+\sqrt{an^{2}+bn+c}}. $

Dzieląc licznik i mianownik otrzymanego ułamka przez $n$ i przechodząc z $n$ do nieskończoności widzimy, że ciąg $(k_{n+1} - k_n)$ jest zbieżny i jego granica wynosi $\sqrt{a}$ . Ponieważ wyrazy ciągu $(k_{n+1} - k_n)$ są całkowite, więc granica tego ciągu, liczba $\sqrt{a}$ , jest też całkowita. Ponadto istnieje taka liczba naturalna $m$ , że

$ (1) \qquad k_{n+1} - k_n = \sqrt{a}\quad \textrm{dla}\ n\geq m. $

Niech $d = k_m - m\sqrt{a}$ . Ze związku (1) wynika, że

$ (2) \qquad k_n = n\sqrt{a}+d \quad \textrm{dla}\ n\geq m. $

Przyjmijmy: $p(x) = (x\sqrt{a} + d)^2$ . Na mocy definicji liczb $k_n$ oraz równości (2) uzyskujemy równość $p(n) = w(n)$ dla $n \geq m$ . To oznacza, że $p(x) = w(x)$ , skąd

$ w(x)=(x\sqrt{a}+d)^2. $

LI OM - III etap

III etap LI Olimpiady Matematycznej

Załącznik	Wielkość
LI OM III etap - Zadania [4]	59.2 KB
LI OM III etap - Zadania z rozwiązaniami [5]	159.2 KB

LI OM - III - Zadanie 1

Zawody matematyczne:

LI OM, 1999-2000

Etap:

III

Dana jest liczba całkowita $n \geq 2$ .

Wyznaczyć liczbę rozwiązań $(x_1,x_2,\ldots,x_n)$ układu równań

$ \left\{\begin{array}{c} x_{2}+x_{1}^{2}=4x_{1}\\ x_{3}+x_{2}^{2}=4x_{2}\\ x_{4}+x_{3}^{2}=4x_{3}\\ \vdots\\ x_{n}+x_{n-1}^{2}=4x_{n-1}\\ x_{1}+x_{n}^{2}=4x_{n} \end{array}\right. $

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 \leq 0, $

skąd wynika, że $x_1 \leq 4$ . Istnieje więc dokładnie jedna liczba $\alpha \in \langle 0,\pi/2\rangle$ , spełniająca zależność $x_1 =4\sin^2 \alpha$ .

Wówczas $x_{2}=x_{1}(4-x_{1})=4\sin^{2}\alpha\cdot 4\cos^{2}\alpha=4\sin^{2}2\alpha$ . Rozumując analogicznie dostajemy

$ x_{k}=4\sin^{2}(2^{k-1}\alpha)\ (k=3,4, \ldots,n) $

oraz $x_{1}=4\sin^{2}(2^{n}\alpha)$ .

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

$ \sin^2 \alpha = \sin^2 (2^n\alpha) $

w liczbach rzeczywistych $\alpha \in \langle 0,\pi/2\rangle$ . Ponieważ równość $\sin\beta=\pm\sin\gamma$ zachodzi wtedy i tylko wtedy, gdy któraś z liczb $\beta+\gamma$ , $\beta-\gamma$ jest całkowitą wielokrotnością $\pi$ , więc jedna z liczb $(2^n+1)\alpha$ , $(2^n-1)\alpha$ musi być całkowitą wielokrotnością $\pi$ . Stąd wynika, że $\alpha$ jest jedną z liczb:

$ 0,\ \frac{k\pi}{2^{n}+1},\ \frac{\ell\pi}{2^{n}-1},\ \text{gdzie}\ k\ \in\{1,2,\ldots,2^{n-1}\},\ \ell\in\{1,2, \ldots,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 $\alpha$ są różne. Zatem istnieje dokładnie $2^n$ ciągów liczb nieujemnych $(x_1,x_2,\ldots,x_n)$ spełniających dany układ równań.

LI OM - III - Zadanie 2

Zawody matematyczne:

LI OM, 1999-2000

Etap:

III

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

$ \measuredangle APM + \measuredangle BPC =180^\circ. $

Rozwiązanie

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

Niech $Q \neq C$ będzie punktem przecięcia okręgu opisanego na trójkącie $BCP$ z prostą $CM$ (rys. 1 i 2). Ponieważ $\measuredangle PAM = \measuredangle PBC = \measuredangle PQC$ , więc punkty $A$ , $P$ , $M$ , $Q$ leżą na jednym okręgu. Ponadto

$ (1) \qquad \measuredangle BPC = \measuredangle BQC = \measuredangle AQC. $

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

$ \measuredangle APM + \measuredangle BPC = \measuredangle APM + \measuredangle AQC = 180^\circ. $

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

$ \measuredangle APM + \measuredangle BPC = \measuredangle AQM + \measuredangle AQC = 180^\circ. $

Załóżmy teraz, że punkt $P$ znajduje się wewnątrz trójkąta $BCM$ . Ponieważ $\measuredangle PBA = \measuredangle PAC$ , więc przeprowadzając rozumowanie analogiczne do powyższego otrzymujemy równość $\measuredangle BPM + \measuredangle APC = 180^\circ$ . Stąd

$ \measuredangle APM + \measuredangle BPC = 180^\circ, $

co kończy

Rozwiązanie

zadania.

LI OM - III - Zadanie 4

Zawody matematyczne:

LI OM, 1999-2000

Etap:

III

W ostrosłupie prawidłowym o wierzchołku $S$ i podstawie $A_1A_2\ldots A_n$ każda krawędź boczna tworzy z płaszczyzną podstawy kąt $60^\circ$ . Dla każdej liczby naturalnej $n \geq 3$ rozstrzygnąć, czy można wybrać takie punkty $B_2,B_3,\ldots,B_n$ leżące odpowiednio na krawędziach $A_2S, A_3S,\ldots,A_nS$ , że

$ A_1B_2 + B_2B_3 + B_3B_4 +\ldots + B_{n-1}B_n + B_nA_1 < 2A_1S. $

Rozwiązanie

Takie punkty istnieją dla dowolnego $n \geq 3$ .

Niech $O$ będzie spodkiem wysokości ostrosłupa, zaś $\alpha$ miarą kąta ściany bocznej przy wierzchołku $S$ . Z równości $A_1S = 2A_1O$ otrzymujemy

$ \sin\frac{\alpha}{2}=\frac{A_{1}A_{2}}{2A_{1}S}=\frac{1}{2}\cdot\frac{A_{1}A_{2}}{2A_{1}O}=\frac{1}{2}\sin\frac{180^{\circ}}{n}=\sin\frac{90^{\circ}}{n}\cos\frac{90^{\circ}}{n}<\sin\frac{90^{\circ}}{n}, $

skąd

$ (1)\qquad n\alpha< 180^\circ. $

Rozetnijmy powierzchnię boczną ostrosłupa wzdłuż krawędzi $A_1S$ i rozłóżmy ją na płaszczyźnie. Otrzymamy wtedy wielokąt $S'A'_1A'_2...A'_nA''_1$ (rys. 1). Na mocy nierówności (1), $\measuredangle A'_1S'A''_1 = n\alpha< 180^\circ$ .

Niech $B'_2,B'_3,\ldots,B'_n$ będą punktami przecięcia odcinka $A'_1A''_1$ odpowiednio z odcinkami $A'_2S',A'_3S',\ldots,A'_nS'$ . Na mocy nierówności trójkąta,

$ A'_1B'_2 + B'_2B'_3 + B'_3B'_4 +\ldots + B'_{n-1}B'_n + B'_nA''_1 < 2A'_1S'. $

Punkty $B'_2,B'_3,\ldots,B'_n$ wyznaczają więc punkty $B_2,B_3,\ldots,B_n$ na krawędziach ostrosłupa spełniające warunki zadania.

LI OM - III - Zadanie 5

Zawody matematyczne:

LI OM, 1999-2000

Etap:

III

Dla danej liczby naturalnej $n \geq 2$ znaleźć najmniejszą liczbę $k$ o następującej własności. Z dowolnego $k$ -elementowego zbioru pól szachownicy $n \times 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:

Z dowolnego zbioru złożonego z $m + n$ pól szachownicy o wymiarach $m \times n$ ( $m,n \geq 2$ ) można wybrać niepusty podzbiór mający w każdym wierszu i w każdej kolumnie szachownicy parzystą liczbę pól.
Istnieje zbiór $m+n-1$ pól szachownicy o wymiarach $m \times 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 \times n$ . Możliwe są następujące trzy przypadki:

istnieje wiersz lub kolumna szachownicy $S$ nie zawierająca żadnego pola ze zbioru $A$ ;
istnieje wiersz lub kolumna szachownicy $S$ , w której znajduje się dokładnie jedno pole ze zbioru $A$ ;
w każdym wierszu i w każdej kolumnie znajdują się co najmniej dwa pola ze zbioru $A$ .

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).

Rozpatrzmy przypadek (c). Niech $k_1,k_2,\ldots,k_n, w_1,w_2,\ldots,w_m$ oznaczają odpowiednio liczby pól zbioru $A$ w poszczególnych kolumnach i wierszach. Wówczas

$ (k_1 + k_2 +\ldots + k_n) + (w_1 + w_2 +\ldots + w_m) = 2(m + n). $

Ponadto $k_i,w_j \geq 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 \times 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$ .

LI OM - III - Zadanie 6

Zawody matematyczne:

LI OM, 1999-2000

Etap:

III

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 \geq -1$ możemy zapisać w postaci $x = y^2 - 1$ , dla pewnej liczby rzeczywistej $y$ . Stąd

$ (1) \qquad P (x) = P (y^2 - 1) = (P (y))^2 - 1 \geq - 1. $

Określamy rekurencyjnie ciąg $(x_n)$ wzorami:

$ x_1 = 1\quad \textrm{oraz}\quad x_n = \sqrt{x_{n-1} + 1}\quad \textrm{dla}\quad n \geq 2. $

Udowodnimy indukcyjnie, że

$ (2)\qquad P(x_n)= x_n\ \textrm{dla}\ n \in\mathrm{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 \geq 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 \in \mathbb{R}$ .