LIX OM - III etap

III etap LIX Olimpiady Matematycznej

Załącznik	Wielkość
LIX OM III etap - Zadania [1]	68.08 KB
LIX OM III etap - Zadania z rozwiązaniami [2]	291.06 KB

LIX OM - III -Zadanie 1

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

W pola tablicy rozmiaru $n \times n$ wpisane są liczby $1, 2, \dots , n^2$ , przy czym liczby $1, 2, \dots , n$ znajdują
się w pierwszym wierszu (od strony lewej do prawej), liczby $n +1, n +2, \dots ,2n$ w drugim, itd.

Wybrano $n$ pól tablicy, z których żadne dwa nie leżą w jednym wierszu ani w jednej kolumnie. Niech $a_i$ będzie liczbą
znajdującą się w tym wybranym polu, które leży w wierszu o numerze $i$ . Dowieść, że

$ \frac{1^2}{a_1} + \frac{2^2}{a_2} + \dots + \frac{n^2}{a_n} \geqslant \frac{n+2}{2} - \frac{1}{n^2+1} $

Rozwiązanie

Udowodnimy najpierw, że

$ (1) \qquad a_1 +a_2 + \dots +a_n = \frac{1}{2} n(n^2 +1). $

Niech $b_i$ oznacza numer kolumny, w której znajduje się liczba $a_i$ . Wówczas

$ (2) \qquad a_i =(i - 1)n +b_i \text{ dla }i =1, 2, \dots, n. $

Z warunków zadania wynika, że ciąg $(b_1,b_2,\dots ,b_n)$ jest permutacją ciągu $(1, 2,\dots ,n)$ . Wobec tego

$ b_1 +b_2 +\dots +b_n =1+2+\dots +n = \frac{1}{2}n(n+1) $

i z uwagi na wzór (2) dowód zależności (1) sprowadza się do rachunku

$ \begin{split} a_1 +a_2 +\dots + a_n &= (0+1+\dots +(n - 1))n +b_1 +b_2 +\dots +b_n = \\ &= \frac{1}{2}(n - 1)n^2 + \frac{1}{2}n(n +1) = \frac{1}{2}n(n^2 +1). \end{split} $

Korzystając teraz z równości (1) oraz z nierówności pomiędzy średnią arytmetyczną i harmoniczną otrzymujemy

$ \begin{split} \frac{1^2}{a_1}+\frac{2^2}{a_2}+\frac{3^2}{a_3}+\dots +\frac{n^2}{a_n} &= \frac{1}{a_1} + \frac{2}{a_2} + \frac{2}{a_2} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{4}{a_4} + \dots \frac{n}{a_n} \geqslant \\ &\geqslant \frac{(1+2+3+\dots +n)}{\frac{1}{a_1} + \frac{2}{a_2} + \frac{2}{a_2} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{3}{a_3} + \frac{4}{a_4} + \dots \frac{n}{a_n}} = \\ &= \frac{\left(\frac{n(n+1)}{2}\right)^2}{a_1+a_2+a_3+\dots+a_n} = \frac{\frac{1}{4}n^2(n+1)^2}{\frac{1}{2}n(n^2+1)} = \\ &= \frac{n(n+1)^2}{2(n^2+1)} = \frac{(n+2)(n^2+1)-2}{2(n^2+1)} \\ &= \frac{n+2}{2} - \frac{1}{n^2+1} \end{split} $

czyli tezę zadania.

LIX OM - III -Zadanie 2

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

Funkcja $f(x, y, z)$ trzech zmiennych rzeczywistych spełnia dla dowolnych liczb rzeczywistych $a, b, c, d, e$ zależność

$ f (a, b, c)+f (b, c, d)+f (c, d, e)+f (d, e, a)+f (e, a, b)= a +b + c +d +e. $

Dowieść, że dla dowolnych liczb rzeczywistych $x_1, x_2, \dots, x_n$ ( $n \geqslant 5$ ) prawdziwa jest równość

$ f(x_1 ,x_2 ,x_3 )+f(x_2 ,x_3 ,x_4 )+\dots +f(x_n ,x_1 ,x_2 )= x_1 +x_2 + \dots +x_n . $

Rozwiązanie

Podstawiając $a = b = c = d = e = 0$ w danym w treści zadania warunku dostajemy $f(0, 0, 0) = 0$ .

Niech teraz $s, t, u$ będą dowolnymi liczbami rzeczywistymi. Wówczas

$ \begin{split} f (s, t, u)+ f (t, u, 0)+f (u, 0, 0)+f (0, 0,s)+f (0, s, t) &= s +t +u, \\ f (0, t, u)+f (t, u, 0)+f (u, 0, 0)+f (0, 0, 0)+f (0, 0,t) &= t + u. \end{split} $

Odejmując powyższe dwie równości stronami i wykorzystując udowodnioną wcześniej równość $f (0, 0, 0) = 0$ otrzymujemy

$ (1) \qquad f (s, t, u)= s +f (0, 0,t)- f (0, 0,s)+f (0, t, u)- f (0, s, t). $

Wypisując równość (1) dla trójek $(s, t, u)=(x_k ,x_{k+1},x_{k+2})$ dla $k =1, 2,\dots ,n$ (gdzie przyjmujemy
$x_{n+1} = x_1, x_{n+2} = x_2$ ) i sumując stronami uzyskanych w ten sposób $n$ równości dostajemy tezę zadania.

LIX OM - III -Zadanie 3

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

W pięciokącie wypukłym $ABCDE$ , w którym $BC = DE$ , zachodzą równości

$ \measuredangle ABE = \measuredangle CAB = \measuredangle AED - 90^{\circ} \text{ oraz }\measuredangle ACB = \measuredangle ADE. $

Dowieść, że czworokąt $BCDE$ jest równoległobokiem.

Rozwiązanie

Zauważmy przede wszystkim (rys. 1), że jeżeli punkt I jest środkiem okręgu wpisanego w trójkąt XY Z, to zachodzi równość

$ \measuredangle XIY = 90^{\circ} + \frac{1}{2} \measuredangle Z. $

Dla dowodu wystarczy zobaczyć, że

$ \measuredangle IXY = \frac{1}{2}\measuredangle X, \; \measuredangle IYX = \frac{1}{2}\measuredangle Y, $

a więc

$ \begin{split} \measuredangle XIY &= 180^{\circ} - \frac{1}{2}\measuredangle X - \frac{1}{2}\measuredangle Y = \\ &= 180^{\circ} - (90^{\circ} - \frac{1}{2}\measuredangle Z) = 90^{\circ} + \frac{1}{2}\measuredangle Z. \end{split} $

Przechodzimy do rozwiązania zadania. Oznaczmy

$ \alpha = \measuredangle ADE = \measuredangle ACB, \quad \beta = \measuredangle ABE = \measuredangle CAB. $

Niech $o$ oznacza okrąg o środku w punkcie $B$ styczny do prostej $AC$ (rys. 2). Niech ponadto styczne do okręgu o przechodzące
przez punkty $A$ i $C$ (różne od prostej $AC$ ) przecinają się w punkcie $F$ . Punkt ten leży po tej samej stronie prostej $AC$ ,
co punkt $B$ , gdyż $\measuredangle BAC +\measuredangle BCA = \alpha + \beta < 90^{\circ}$ ze względu na to, że $\alpha$ i
$90^{\circ} +\beta$ są kątami wewnętrznymi trójkąta $DEA$ .

Wówczas okrąg o jest wpisany w trójkąt AFC, zatem na mocy początkowej obserwacji mamy

$ \measuredangle FBC = 90^{\circ} + \frac{1}{2}\measuredangle FAC = 90^{\circ} +\beta = \measuredangle AED. $

Ponieważ także $\measuredangle FCB = \measuredangle ACB = \alpha = \measuredangle ADE$ oraz $BC = DE$ , więc trójkąty
$FBC$ i $AED$ są przystające (cecha kąt-bok-kąt) i jednakowo zorientowane. To oznacza, że spełniona jest równość
$FB = AE$ . Zauważmy następnie, że

$ \measuredangle BAF = \measuredangle BAC = \beta = \measuredangle ABE. $

W efekcie proste $AF$ i $EB$ są równoległe; wraz z zależnością $FB =AE$ daje to, że czworokąt $AFBE$ jest
trapezem równoramiennym albo równoległobokiem.

Pierwsza z tych ewentualności zachodzić jednak nie może, gdyż na podstawie spostrzeżenia z początku rozwiązania oznaczałaby ona, że

$ \measuredangle AEB = \measuredangle EBF = \measuredangle EBA +\measuredangle ABF = \beta +90^{\circ} +\alpha, $

skąd uzyskalibyśmy

$ 90^{\circ} +\beta = \measuredangle AED > \measuredangle AEB = 90^{\circ} +\beta +\alpha, $

a to jest oczywista niedorzeczność. Zatem czworokąt $AFBE$ jest równoległobokiem, czyli proste $AE$ i $BF$ są
równoległe. To dowodzi, że trójkąt $FBC$ powstaje z trójkąta $AED$ w wyniku przesunięcia o wektor $EB$ . Zatem odcinki
$ED$ i $BC$ również są równoległe, a to z uwagi na równość ich długości pociąga za sobą tezę zadania.

LIX OM - III -Zadanie 4

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

Każdy punkt płaszczyzny o obu współrzędnych całkowitych pomalowano na biało albo na czarno. Dowieść, że ze zbioru w
szystkich pomalowanych punktów można wybrać nieskończony podzbiór, który ma środek symetrii i którego wszystkie punkty
mają ten sam kolor.

Rozwiązanie

Przypuśćmy, że teza zadania jest fałszywa.

Rozpatrzmy symetrię środkową względem punktu $(0,0)$ . Ponieważ nie istnieje nieskończony zbiór symetryczny względem
tego punktu i złożony z punktów jednego koloru, więc tylko skończenie wiele punktów o obu współrzędnych całkowitych
przechodzi przy tej symetrii na punkty tego samego koloru. Wobec tego istnieje taka liczba całkowita $M$ , że dla każdego
punktu o współrzędnych całkowitych $(x,y)$ , przy czym $|y| >M$ , punkty $(-x,-y)$ i $(x,y)$ mają różne kolory.

Rozważając analogicznie symetrię środkową względem punktu $(\frac{1}{2},0)$ widzimy, że istnieje taka liczba całkowita $N$ ,
że dla każdego punktu o współrzędnych całkowitych $(x,y)$ , przy czym $|y|>N$ , punkt $(x,y)$ ma inny kolor niż jego obraz
przez rozpatrywaną symetrię, czyli punkt $(-x+1,-y)$ .

Przyjmijmy $k =\max\{M,N\}+1$ i rozpatrzmy dowolną liczbę całkowitą $s$ . Wówczas punkt $(s,k)$ przy symetrii względem
punktu $(0,0)$ przechodzi na punkt $(-s,-k)$ , który jest przeciwnego koloru niż punkt $(s,k)$ . Ponadto punkt $(-s,-k)$
przy symetrii względem punktu $(\frac{1}{2}, 0)$ przechodzi na punkt $(s +1,k)$ , który jest przeciwnego koloru niż punkt $(-s,-k)$ .
Wobec tego punkty $(s,k)$ i $(s+1,k)$ mają jednakowy kolor. Ponieważ $s$ było dowolną liczbą całkowitą, więc wynika stąd,
że wszystkie punkty o pierwszej współrzędnej całkowitej i drugiej współrzędnej równej $k$ mają ten sam kolor.
Jednakże punkty te tworzą nieskończony zbiór, którego środkiem symetrii jest punkt $(0,k)$ .
Otrzymana sprzeczność z założeniem nie wprost kończy rozwiązanie.

LIX OM - III -Zadanie 5

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

Pola wszystkich przekrojów równoległościanu $\mathcal{R}$ płaszczyznami przechodzącymi przez środki trzech jego krawędzi,
z których żadne dwie nie są równoległe i nie mają punktów wspólnych, są równe. Udowodnić, że równoległościan
$\mathcal{R}$ jest prostopadłościanem.

Rozwiązanie

Przyjmijmy, że pola wszystkich przekrojów, o których mowa w treści zadania, są równe $S$ .

Niech $ABCD$ i $EFGH$ będą podstawami równoległościanu $\mathcal{R}$ (rys. 3), niech $O$ będzie jego środkiem
symetrii i niech $I, J, K, L, M, N$ oznaczają odpowiednio środki krawędzi $AE, EF , FG, GC, CD, DA$ . Wówczas następujące
pary punktów: $I$ i $L$ , $J$ i $M$ , $K$ i $N$ $, są symetryczne względem punktu $O$ .

Płaszczyzna $\pi$ przechodząca przez punkty $I, K, M$ w przekroju z równoległościanem $\mathcal{R}$ wyznacza figurę
o polu $S$ . Wykażemy, że figurą tą jest sześciokąt $IJKLMN$ .

Oznaczmy przez $\pi'$ płaszczyznę przechodzącą przez punkty $I, N, M$ . Na mocy twierdzenia odwrotnego do twierdzenia
Talesa mamy $NM || AC || IL$ . Prosta $NM$ i punkt $I$ leżą w płaszczyźnie $\pi'$ , zatem prosta przechodząca przez punkt
$I$ i równoległa do prostej $NM$ (czyli prosta $IL$ ) również leży w płaszczyźnie $\pi'$ . Stąd wniosek, że środek $O$ odcinka
$IL$ leży w płaszczyźnie $\pi'$ . To z kolei oznacza, że punkty $J$ i $K$ , symetryczne względem punktu $O$ odpowiednio do punktów
$M$ i $N$ , również leżą w płaszczyźnie $\pi'$ . Skutkiem tego punkty $I, J, K, L, M, N$ leżą w tej płaszczyźnie; tworzą one
więc płaski sześciokąt o środku symetrii O.

Ponadto płaszczyzny $\pi$ i $\pi'$ mają trzy niewspółliniowe punkty wspólne: $I, K$ oraz $M$ . To dowodzi, że
$\pi = \pi'$ .

Udowodniliśmy w ten sposób, że punkt $O$ jest środkiem symetrii sześciokąta $IJKLMN$ o polu $S$ . Zatem czworokąt $ILMN$
ma pole równe $\frac{1}{2}S$ ; jest on ponadto trapezem, gdyż wykazaliśmy wcześniej, że proste $IL$ i $MN$ są równoległe.
Jeżeli przez $P$ i $Q$ oznaczymy odpowiednio środki krawędzi $AB$ i $BC$ , to przeprowadzając analogiczne rozumowanie uzasadniamy,
że czworokąt $ILQP$ jest trapezem o polu $\frac{1}{2}S$ .

Trapezy $ILMN$ i $ILQP$ mają więc równe pola; mają one ponadto wspólną podstawę $IL$ oraz równe drugie podstawy
( $NM = PQ = \frac{1}{2}AC$ ). Wynika stąd, że trapezy te mają równe wysokości. Inaczej mówiąc, odległości prostej
$IL$ od prostych $NM$ i $PQ$ są jednakowe.

Jeżeli $l_1, l_2$ są różnymi równoległymi prostymi w przestrzeni, to każda prosta do nich równoległa i jednakowo od nich
oddalona jest zawarta w płaszczyźnie $\Pi$ , względem której proste $l_1$ i $l_2$ są symetryczne. Płaszczyzna $\Pi$ jest ponadto
prostopadła do płaszczyzny wyznaczonej przez proste $l_1$ i $l_2$ .

Wobec tego proste $AC$ i $IL$ , równoodległe od prostych $NM$ i $PQ$ , wyznaczają płaszczyznę prostopadłą do płaszczyzny
$MNPQ$ . Innymi słowy, płaszczyzna $\pi_1$ zawierająca równoległobok $ACGE$ jest prostopadła do podstawy $ABCD$ . Analogicznie
wykazujemy, że płaszczyzna $\pi_2$ zawierająca równoległobok $BFHD$ jest prostopadła do podstawy $ABCD$ . Stąd wniosek, że
krawędź płaszczyzn $\pi_1$ i $\pi_2$ , która jest prostą równoległą do $AE$ , jest prostopadła do podstawy $ABCD$ .
Otrzymujemy stąd równości $\measuredangle EAB = \measuredangle EAD = 90^{\circ}$ .

Podobnie dowodzimy, że $\measuredangle DAB = 90^{\circ}$ . Zatem równoległościan $\mathcal{R}$ jest prostopadłościaniem.

LIX OM - III -Zadanie 6

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

III

Niech $S$ będzie zbiorem wszystkich dodatnich liczb całkowitych, które można przedstawić w postaci $a^2 +5b^2$
dla pewnych względnie pierwszych liczb całkowitych $a$ i $b$ . Niech ponadto $p$ będzie liczbą pierwszą dającą resztę
3 z dzielenia przez 4. Wykazać, że jeżeli pewna dodatnia wielokrotność liczby $p$ należy do zbioru $S$ , to również liczba
$2p$ należy do zbioru $S$ .

Rozwiązanie

Na mocy warunków zadania liczba $a^2 +5b^2$ jest podzielna przez $p$ dla pewnych względnie pierwszych liczb całkowitych $a$ i $b$ .

Liczba $b$ nie jest podzielna przez $p$ ; w przeciwnym przypadku z podzielności $p|b$ oraz $p|a^2 +5b^2$ uzyskalibyśmy bowiem
$p|a$ , wbrew względnej pierwszości liczb $a$ i $b$ .

Zatem żadna z $p - 1$ liczb: $b,2b, \dots ,(p - 1)b$ nie jest podzielna przez $p$ . Ponadto liczby te dają różne reszty
z dzielenia przez $p$ . Istotnie, jeżeli mamy $p| ib-jb=(i-j)b$ dla pewnych wskaźników $1\leqslant i,j \leqslant p-1$ , to liczba
pierwsza $p$ jest dzielnikiem różnicy $i - j$ , skąd wynika, że $i = j$ . W konsekwencji jedna z rozpatrywanych liczb daje
resztę 1 z dzielenia przez $p$ . Przyjmijmy, że jest to liczba $kb$ (dla pewnej wartości $k \in\{1,2,\dots ,p- 1\}$ ). Wówczas
mamy

$ p| k^2(a^2 +5b^2)=(ak)^2 +5(bk)^2,\quad \text{czyli} \quad p| m^2 +5, \quad \text{gdzie} m = ak. $

Niech $z$ oznacza największą liczbę całkowitą nie przekraczającą $p$ . Rozpatrzmy zbiór reszt z dzielenia liczb
$0, m,2m, \dots , zm$ przez $p$ . Uporządkujmy te $z +1$ reszt w kolejności niemalejącej otrzymując ciąg
$r_1 \leqslant r_2 \leqslant \dots \leqslant r_z+1$ . Wtedy każda z $z +1$ liczb:

$ r_2 - r_1, \; r_3 - r_2,\; \dots , r_{z+1} - r_z,\; p- (r_{z+1} - r_1) $

jest nieujemna, a ich suma wynosi $p$ . Wynika stąd, że przynajmniej jedna z tych liczb jest nie większa niż

$ \frac{p}{z+1}=\frac{(z+(p-z))^2}{z+1}< \frac{(z+1)^2}{z+1} = z+1 $

Zatem wśród liczb $r_2 -r_1, r3 -r2, \dots , r_{z+1} -r_z , p-(r_{z+1} -r_1)$ można wskazać liczbę nie przekraczającą
$z$ . To zaś oznacza, że pewne dwie różne liczby, powiedzmy $cm$ i $dm$ ( $0 \leqslant c,d \leqslant z$ ), dają przy dzieleniu
przez $p$ reszty różniące się nie więcej niż o $z$ , albo różniące się przynajmniej o $p - z$ . Przyjmijmy $y = |c - d|$ ;
wówczas jedna z liczb $ym, -ym$ daje resztę $x \leqslant z$ z dzielenia przez $p$ . Ponieważ $p | m^2 +5$ , więc liczby

$ x^2 +5y^2 \text{ i } x^2 - m^2y^2 =(x - my)(x +my) $

dają taką samą resztę z dzielenia przez $p$ . Jeden z czynników $x - my, x+my$ jest jednak podzielny przez $p$ .
W efekcie $p | x^2 +5y^2$ . Ponadto $0 \leqslant x \leqslant z$ oraz $0 \leqslant y \leqslant z$ , co w połączeniu
z nierównością $z< p$ daje

$ x^2 +5y^2 \leqslant 6z^2 < 6( \sqrt{p})2 =6p. $

Stąd wniosek, że $x^2 +5y^2$ jest jedną z liczb $p,2p,3p,4p$ lub $5p$ .

Równość $x^2 +5y^2= p$ oznaczałaby, że liczba $x^2 +5y^2$ daje resztę 3 z dzielenia przez 4. To jednak nie jest możliwe,
gdyż liczby $x$ i $5y^2$ dają reszty 0 lub 1 z dzielenia przez 4. Zatem $x^2 +5y^2 = p$ . To dowodzi także, że nie mogą mieć
miejsca równości $x^2 +5y^2=4p$ ani $x^2 +5y^2=5p$ . Pierwsza z tych równości oznaczałaby bowiem, że liczby
$x$ i $y$ są parzyste (w żadnym innym przypadku liczba $x^2 +5y^2$ nie jest podzielna przez 4) oraz
$(\frac{1}{2}x)^2 +5(\frac{1}{2}y)^2 = p$ ; druga równość prowadzi natomiast do wniosku, że $5|x$ oraz
$y^2 +5(\frac{1}{2}x)^2 = p$ . W obu przypadkach dochodzimy do sprzeczności z udowodnionym wcześniej faktem, że liczba postaci
$^2 +5f^2$ jest różna od $p$ dla dowolnych całkowitych wartości $e$ i $f$ .

Stwierdziliśmy w ten sposób, że $x^2 +5y^2=2p$ lub $x^2 +5y^2=3p$ .

Przypuśćmy, że $x^2 +5y^2 =3p$ . Wówczas liczby $x$ i $y$ nie są podzielne przez 3 (w przeciwnym razie mielibyśmy
$3|x$ oraz $3|y$ , jednakże wówczas $3^2| x^2 +5y^2=3p$ ; co może się zdarzyć jedynie w przypadku $p = 3$ , ale wtedy
uzyskujemy następującą sprzeczność: $9=3p =x^2 +5y^2 \geqslant 3^2 +5\cdot 3^2 =54$ ). Zmieniając ewentualnie znaki
liczb $x$ i $y$ możemy przyjąć, że $x$ i $y$ są liczbami całkowitymi dającymi resztę 1 z dzielenia przez 3. Ponadto

$ 18p =6\cdot 3p = 6(x^2 +5y^2 )=(x +5y)^2 +5(x - y)^2. $

Liczby $x+5y$ i $x-y$ są podzielne przez 3; jeżeli więc $x+5y =3g$ oraz $x-y =3h$ , to z powyższej równości wnioskujemy,
że $2p = g^2 +5h^2$ .

Ostatecznie udowodniliśmy, że liczba $2p$ daje się przedstawić w postaci $s^2 +5t^2$ dla pewnych liczb całkowitych
$s$ i $t$ . Pozostaje zauważyć, że w takiej sytuacji liczby $s$ i $t$ są względnie pierwsze; gdyby bowiem miały one
wspólny dzielnik pierwszy $q$ , to uzyskalibyśmy $q^2 | s^2 +5t^2 =2p$ , co prowadzi do sprzeczności, gdyż
$p$ jest nieparzystą liczbą pierwszą. Zatem dowód relacji $2p \in S$ jest zakończony.