LIX OM

LIX Olimpiada Matematyczna

Załącznik	Wielkość
Informacja o przebiegu LIX Olimpiady Matematycznej [1]	93.95 KB

LIX OM - I etap

I etap LIX Olimpiady Matematycznej

Załącznik	Wielkość
LIX OM I etap - Zadania [2]	109.01 KB
LIX OM I etap - Zadania z rozwiązaniami [3]	188.16 KB

LIX OM - I -Zadanie 1

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Rozwiązać w liczbach rzeczywistych $x, y, z$ układ równań

$ \begin{cases} x^5 =5 y^3 -4z \\ y^5 =5z^3 -4x \\ z^5 =5x^3 -4y \end{cases} $

Rozwiązanie

Jeżeli trójka liczb $(x,y,z)$ spełnia dany układ równań, to spełniają go również trójki liczb
$(y,z,x)$ i $(z,x,y)$ . Zatem bez ograniczenia ogólności rozumowania możemy przyjąć, że $x$ jest
najmniejszą wśród liczb $x, y, z$ (pozostałe rozwiązania otrzymamy przez cykliczne przestawienie zmiennych).

Rozpatrzmy dwa przypadki.

1. $y \leqslant z$ . Mamy więc $x \leqslant y \leqslant z$ . Funkcja
$f(t) = t^5$ jest ściśle rosnąca, zatem z drugiego i trzeciego równania danego układu otrzymujemy

$ 5 z^3 = y^5 +4x \leqslant z^5 +4y =5x^3. $

Funkcja $f(t) = t^3$ również jest ściśle rosnąca. Wobec tego powyższa nierówność implikuje, że
$z\leqslant x$ . W konsekwencji $x= y= z$ . Stąd wynika, że rozwiązania danego układu równań w tym
przypadku mają postać $x= y= z= t$ , gdzie $t$ jest rozwiązaniem równania $t=5 t^3 -4t$ . To równanie jest
równoważne równaniu

$ 0= t^5 -5 t^3 +4t = t(t^4 -5t^2 +4)= t(t^2 -1)(t^2 -4) = t(t-1)(t+1)(t-2)(t+2), $

które ma rozwiązania $t = -2,-1,0,1,2$ . Otrzymujemy więc 5 rozwiązań danego układu równań:
$x= y= z \in {-2,-1,0,1, 2}$ .

2. $y>z$ . W tym przypadku $x \leqslant z<y$ . Rozumując podobnie jak poprzednio uzyskujemy

$ 5 y^3 = x^5 +4z < z^5 +4y =5x^3, $

czyli $y < x$ . Zatem $x \leqslant z < y < x$ , co nie może mieć miejsca. Uwalniając się od założenia,
że $x$ jest najmniejszą wśród liczb $x, y, z$ , widzimy, że jedynymi rozwiązaniami układu są rozwiązania
otrzymane w przypadku 1.

Odpowiedź: Rozwiązaniami $(x,y,z)$ danego układu równań są:

$ (-2,-2,-2),(-1,-1,-1),(0,0,0),(1,1,1),(2,2,2). $

LIX OM - I -Zadanie 2

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dany jest kąt wypukły o wierzchołku $P$ i punkt $A$ leżący wewnątrz tego kąta. Punkty $X$ i $Y$ leżą na różnych
ramionach tego kąta, przy czym $PX = PY$ oraz wartość sumy $AX +AY$ jest najmniejsza. Wykazać, że
$\measuredangle XAP = \measuredangle YAP$ .

Rozwiązanie

Niech $B$ będzie takim punktem płaszczyzny, dla którego $PB = PA$ oraz
$\measuredangle BPA = \measuredangle YPX$ (rys. 1).

Mamy wówczas $\measuredangle BPY = \measuredangle APX$ , zatem trójkąty $BPY$ i $APX$ są przystające
(cecha bok-kąt-bok). Stąd otrzymujemy równość $BY = AX$ . Wartość wyrażenia $AX + AY = BY + AY$
jest najmniejsza, więc stosując nierówność trójkąta dochodzimy do wniosku, że punkt $Y$ leży na odcinku $AB$ .
Ponieważ zaś trójkąt $BPA$ jest równoramienny, uzyskujemy

$ \measuredangle YAP = \measuredangle BAP = \measuredangle ABP = \measuredangle YBP = \measuredangle XAP, $

co kończy rozwiązanie.

LIX OM - I -Zadanie 3

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Ciąg liczb całkowitych $a_1, a_2, a_3, \dots$ jest określony przez warunki: $a_1 = 1, a_2 = 2$ ,

$ (1)\qquad a_n =3a_n-1 +5a_{n-2} \quad\text{ dla }n =3,4,5,\dots . $

Rozstrzygnąć, czy istnieje taka liczba całkowita $k \geqslant 2$ , że liczba $a_k$ jest dzielnikiem
iloczynu $a_{k+1}a_{k+2}$ .

Rozwiązanie

Z danego w treści zadania warunku (1) wynika, że

$ a_{k+1}a_{k+2} = a_{k+1}(3a_k +5a_{k+1})=3a_ka_{k+1} +5a_{k+1}^2 $

dla $k \geqslant 2$ . Wobec tego liczba $a_k$ jest dzielnikiem iloczynu $a_{k+1}a_{k+2}$ wtedy i tylko
wtedy, gdy jest dzielnikiem liczby $5a_{k+1}^2$ .

Zauważmy, że żaden wyraz ciągu $a_1, a_2, a_3, \dots$ nie jest liczbą podzielną przez 5. W istocie,
dla każdego wskaźnika $n\geqslant 3$ z równości $a_n-3a_{n-1} =5a_{n-2}$ wynika, że liczby
$a_n, a_{n-1}$ są obie podzielne przez 5 lub też żadna z nich.

Ponieważ jednak $a_1 =1, a_2 =2$ są liczbami niepodzielnymi przez 5, więc przez prostą indukcję otrzymujemy
żądany wniosek. Analogicznie dowodzimy, że dla dowolnego $n \geqslant 3$ liczby $a_n, a_{n-2}$ są obie
podzielne albo obie niepodzielne przez 3, zatem w danym ciągu nie występują liczby podzielne przez 3.

Pozostaje więc zbadać, czy istnieje taka liczba całkowita $k \geqslant 2$ , że liczba $a_2$ jest podzielna przez
$a_k$ . Ponieważ $a_k \geqslant 2$ , więc oznacza to, że liczby $a_k$ i $a_{k+1}$ muszą mieć wspólny dzielnik
pierwszy $p$ . Jak wykazaliśmy wyżej, liczba $p$ jest różna od 3 i 5. Ponadto istnieje najmniejsza taka liczba
całkowita dodatnia $m$ , że liczby $a_m$ i $a_{m+1}$ są podzielne przez $p$ . Mamy oczywiście $m\geqslant 2$ ,
więc zachodzi równość $5a_{m-1} = a_{m+1} -3a_m$ , z której wnioskujemy, że liczba $a_{m-1}$ jest podzielna
przez $p$ . To jednak przeczy określeniu liczby $m$ .

Uzyskana sprzeczność dowodzi, że taka liczba $k$ nie istnieje.

LIX OM - I -Zadanie 4

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dana jest liczba całkowita $n \geqslant 1$ . Każdemu niepustemu podzbiorowi $A$ zbioru $\{1, 2,\dots ,n\}$
przyporządkowujemy liczbę $w(A)$ w następujący sposób: Jeżeli $a_1 >a_2 >\dots >a_k$ są wszystkimi elementami
zbioru A, to

$ (1)\qquad w(A)= a_1 -a_2 +a_3 -\dots +(-1)^{k+1} a_k. $

Obliczyć sumę wszystkich $2n-1$ otrzymanych liczb $w(A)$ .

Rozwiązanie

Sposób I

Dla $n = 1$ rozważana suma jest równa 1. Przyjmijmy więc, że $n \geqslant 2$ .

Niech $B_1, B_2, \dots , B_m$ będą wszystkimi niepustymi podzbiorami zbioru $\{1, 2,\dots ,n-1\}$ .
Wówczas $m =2^{n-1} -1$ oraz

$ B_1,B_2, \dots , Bm, \{n\},B_1 \cup \{n\},B_2 \cup \{n\}, \dots , B_m \cup \{n\} $

są wszystkimi niepustymi podzbiorami zbioru $\{1, 2,\dots ,n\}$ .

Ustalmy wartość $i\in \{1,2,\dots ,m\}$ . Niech $c_1 >c_2 >\dots >c_k$ będą wszystkimi elementami zbioru $B_i$ . Nietrudno spostrzec, że

$ \begin{split} w(B_i) &= c_1 -c_2 +c_3 -\dots +(-1)^{k+1} c_k, \\ w(B_i \cup \{n\}) &= n-c_1 + c_2 -\dots +(-1)^{k+2} c_k, \end{split} $

zatem

$ (2) \qquad w(B_i)+w(B_i \cup \{n\})= n. $

Wypisując równość (2) dla $i =1,2,\dots ,m$ i sumując stronami uzyskujemy

$ w(B_1)+w(B_1 \cup \{n\})+\dots +w(B_m)+w(B_m \cup \{n\})= m\cdot n. $

Wobec tego suma, którą należy wyznaczyć, jest równa $w({n})+ m\cdot n = n+(2^{n-1} -1)\cdot n = n\cdot 2^{n-1}$ .

Sposób II

Niech $A_1, A_2, \dots , A_m$ ( $m =2^n - 1$ ) będą wszystkimi niepustymi podzbiorami zbioru
$\{1,2,\dots ,n\}$ . Utwórzmy tabelę o $m$ wierszach i $n$ kolumnach. W każde pole tej tabeli wpisujemy
liczbę zgodnie z następującą zasadą: Jeżeli $a_1 >a_2 >\dots >a_k$ są wszystkimi elementami zbioru
$A_j$ (gdzie $j =1,2,\dots ,m$ ), to w pole znajdujące się w $j$ -tym wierszu oraz $a_i$ -tej kolumnie
wpisujemy liczbę $(-1)^{i+1}a_i$ . W pozostałe pola tej tabeli wpisujemy zera.

Na mocy warunku (1) suma liczb znajdujących się w $j$ -tym wierszu tabeli wynosi $w(A_j)$ . To oznacza, że suma
$S$ , która należy obliczyć w zadaniu, jest równa sumie wszystkich liczb w tabeli. Zatem

$ (3)\qquad S = k_1 +k_2 +\dots + k_n, $

gdzie $k_i$ jest sumą liczb znajdujących się w $i$ -tej kolumnie.

Dla każdego ze zbiorów $A_1, A_2, \dots , A_m$ liczba $n$ jest bądź jego największym elementem, bądź też do
niego nie należy. Ponadto liczba tych zbiorów, które zawierają liczbę $n$ , jest równa liczbie podzbiorów
zbioru $\{1,2,\dots ,n-1\}$ , czyli liczbie $2^{n-1}$ . Wynika stąd, że w $n$ -tej kolumnie tabeli znajduje
się $2^{n-1}$ liczb $n$ , a pozostałe liczby są zerami. Zatem $k_n = n\cdot 2^{n-1}$ .

Wykażemy z kolei, że $k_1 = k_2 = \dots = k_{n-1} = 0$ .

Ustalmy wartość $j \in \{1,2,\dots ,n - 1\}$ . Każda liczba występująca w $j$ -tej kolumnie jest równa
0, $j$ albo $-j$ . Musimy wykazać, że liczb $j$ jest tyle samo, co liczb $-j$ . Zauważmy, że w $i$ -tym wierszu
rozważanej kolumny znajduje się liczba $j$ wtedy i tylko wtedy, gdy do zbioru $A_i$ należy liczba $j$
oraz parzysta liczba liczb większych od $j$ (wybranych z $(n - j - 1)$ -elementowego zbioru
$\{j +1,j +2,\dots ,n-1,n\}$ ); liczby mniejsze od $j$ nie mają na to wpływu. Zatem liczba liczb
$j$ w $j$ -tej kolumnie tabeli jest równa

$ (4) \qquad 2^{j-1} \left(\binom{n-j-1}{0} + \binom{n-j-1}{2} + \binom{n-j-1}{4} + \hdots \right), $

przy czym ostatni składnik w powyższej sumie wynosi $\binom{n-j-1}{n-j-1}$ albo $\binom{n-j-1}{n-j-2}$
w zależności od parzystości liczby $n - j -1$ . Podobnie dowodzimy, że liczba liczb $-j$ w $j$ -tej kolumnie
jest równa

$ (5) \qquad 2^{j-1} \left(\binom{n-j-1}{1} + \binom{n-j-1}{3} + \binom{n-j-1}{5} + \hdots \right), $

Liczby (4) i (5) są równe, gdyż na mocy wzoru dwumianowego ich różnica wynosi
$2^{j-1} \cdot (1-1)n-j-1 = 0$ . To kończy dowód równości $k_j = 0$ .

Z udowodnionych zależności otrzymujemy na mocy (3), że $S = n\cdot 2^{n-1}$ .

LIX OM - I -Zadanie 5

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Znaleźć wszystkie takie trójki liczb pierwszych $(p,q,r)$ , że liczby

$ pq + qr + rp \quad \text{oraz} \quad p^3+q^3+r^3-2pqr $

są podzielne przez $p+ q +r$ .

Rozwiązanie

Niech liczby pierwsze $p, q, r$ spełniają żądane warunki. Liczba

$ pq +qr +rp = p(p+q +r)-(p^2 -qr) $

jest podzielna przez $p+q+r$ . Wobec tego liczby $p^2-qr$ oraz $p(p^2-qr)=p^3-pqr$ są również podzielne
przez $p+q+r$ . Analogicznie dowodzimy, że liczby

$ q^3 -pqr \quad \text{oraz} \quad r^3 -pqr $

są podzielne przez $p + q + r$ . Sumując te trzy liczby dostajemy podzielność liczby
$p^3 + q^3 + r^3 -3pqr$ przez $p + q + r$ . Zatem na mocy warunków zadania liczba $p+ q +r$ jest dzielnikiem
liczby $pqr$ .

Liczby $p, q, r$ są pierwsze, więc wszystkimi dodatnimi dzielnikami liczby pqr są:
$1, p, q, r, pq, qr, rp, pqr$ (przy czym niektóre z nich mogą być równe). To oznacza, że $p + q + r$
musi być równe jednemu z tych dzielników. Cztery pierwsze dzielniki są mniejsze od $p + q + r$ . Ponadto
$pqr >p + q + r$ , gdyż ze względu na nierówności $p,q,r \geqslant 2$ mamy

$ pqr \geqslant 4\cdot \max\{p,q,r\} > 3\cdot \max\{p,q,r\}\geqslant p+q +r. $

Zatem liczba $p+q+r$ jest równa $pq$ , $qr$ lub $rp$ . Dla ustalenia uwagi przyjmijmy, że
$p+q +r = pq$ . Liczba $pq +qr +rp$ jest więc podzielna przez $pq$ . Stąd liczba

$ pq(p+q +1)-(pq +qr +rp)=(p+ q)(pq -r)=(p+ q)^2 $

dzieli się przez $pq$ . To oznacza, że liczba $p + q$ jest podzielna przez liczby pierwsze
$p$ i $q$ . Musi więc być $p = q$ . Ponadto $r = pq -p-q = p^2 -2p = p(p-2)$ jest liczbą pierwszą.
Wobec $p \geqslant 2$ iloczyn $p(p - 2)$ może być liczbą pierwszą jedynie wtedy, gdy
$p-2 = 1$ . Ostatecznie mamy $p = q =3$ i $r =3\cdot 1 = 3$ .

Pozostaje bezpośrednio sprawdzić, że otrzymane liczby spełniają warunki zadania.

Odpowiedź: Jedynym rozwiązaniem są liczby $(p,q,r) = (3,3,3)$ .

Uwaga

W powyższym rozwiązaniu udowodniliśmy, że liczba $p^3 + q^3 + r^3 -3pqr$ jest podzielna przez
$p + q + r$ . Można tę podzielność również wykazać przy użyciu tożsamości

$ x^3 +y^3 +z^3 -3xyz =(x +y +z)(x^2 +y^2 +z^2 -xy -yz -zx). $

LIX OM - I -Zadanie 6

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Wyznaczyć wszystkie takie wielomiany $W(x)$ o współczynnikach rzeczywistych, że dla każdej liczby
rzeczywistej $x$ spełniona jest równość

$ (1) \qquad W(x^2)\cdot W (x^3)=(W (x))^5. $

Rozwiązanie

Sposób I

Zauważmy najpierw, że jedynymi wielomianami stałymi spełniającymi warunki zadania są $W(x) \equiv 0$ oraz
$W(x) \equiv 1$ . Przyjmijmy więc dalej, że wielomian $W(x)$ nie jest stały.

Jeżeli wielomian $W(x)$ jest postaci $W(x)=cx^n$ dla pewnej liczby rzeczywistej $c \neq 0$
i liczby całkowitej $n \geqslant 1$ , to w warunku (1) mamy

$ W(x^2)\cdot W(x^3)= c^2 x^{5n} =(W(x))^5 = c^5 x^{5n} , $

co implikuje $c^2=c^5$ i $c=1$ . Wobec tego wśród wielomianów rozważanej postaci tylko wielomiany
$W(x)= x$ dla $n \geqslant 1$ spełniają warunki zadania.

Pozostał do rozpatrzenia przypadek, gdy wielomian $W(x)$ jest sumą co najmniej dwóch niezerowych
jednomianów. W takim razie możemy napisać

$ W(x)= a_nx^n +a_lx^l +G(x), $

gdzie $n>l \geqslant 0$ , $a_n \neq 0$ , $a_l \neq 0$ , a wielomian $G(x)$ jest wielomianem zerowym albo ma stopień najwyżej $l -1$ . Zatem

$ \begin{split} W(x^2)\cdot W(x^3)&=(a_nx^{2n} +a_lx^{2l} +G(x^2))(a_nx^{3n} +a_lx^{3l} +G(x^3)) \\ &= a_n^2 x^{5n} + a_la_n x^{3n+2l} + a_la_n x^{2n+3l} + P(x), \end{split} $

gdzie $P(x)$ jest wielomianem stopnia co najwyżej $2n+3l -1$ , oraz

$ (W(x))^5 =(a_nx^n +a_lx^l +G(x))^5 = a_n^5x^{5n} +5a_na_lx^{4n+l}+Q(x), $

gdzie $Q(x)$ jest wielomianem stopnia co najwyżej $3n +2l$ . Liczby $2n +3l$ i $3n+2l$
są mniejsze od $4n+l$ . Wobec tego współczynnik przy potędze $x^{4n+l}$ w wielomianie
$W(x^2)\cdot W(x^3)$ jest równy zeru, a w wielomianie $(W(x))^5$ wynosi on $5a_na_l \neq 0$ .
Doszliśmy więc do sprzeczności.

Sposób II

Tak jak w sposobie I rozpatrujemy najpierw przypadek, gdy wielomian $W(x)$ jest stały.
Otrzymujemy więc rozwiązania $W(x)\equiv 0$ i $W(x)\equiv 1$ ,a w dalszej części rozwiązania
przyjmujemy, że wielomian $W(x)$ nie jest stały.

Podstawiając $x = 0$ w zależności (1) otrzymujemy $(W(0))^2 =(W(0))^5$ . Zatem
$W(0)=0$ albo $W(0) = 1$ .

Przypuśćmy najpierw, że $W(0) = 1$ . Wielomian $W(x)-1$ nie jest stały i jego pierwiastkiem jest liczba $x=0$ . Wobec tego istnieją taka liczba całkowita dodatnia $k$ oraz taki wielomian $G(x)$ , że

$ W(x)=1+x^k \cdot G(x),\quad \text{przy czym } G(0) \neq 0. $

Korzystając ze wzoru dwumianowego obliczamy, że

$ \begin{split} W (x 2)\cdot W (x 3) &= (1+x^{2k}G(x^2))(1+x^{3k}G(x^3)) = 1+x^{2k}P(x), \\ (W(x))^5 &= (1+x^kG(x))^5 = 1+5x^kG(x)+x^{2k}Q(x), \end{split} $

gdzie $P(x), Q(x)$ są pewnymi wielomianami o współczynnikach rzeczywistych. Jeżeli więc równość (1) zachodzi dla każdej liczby rzeczywistej $x$ , to

$ (2) \qquad x^{2k}(P(x)-Q(x)) = x^k \cdot G(x) $

dla wszystkich $x$ . Jednakże wielomian występujący po lewej stronie równości (2) jest podzielny przez
$x^{2k}$ , a wielomian po prawej stronie zawiera niezerowy współczynnik $G(0)$ przy potędze $x^k$ .
Otrzymaliśmy więc sprzeczność.

Pozostaje więc do rozpatrzenia przypadek $W(x) \neq 0$ , $W(0)=0$ . Wówczas możemy napisać

$ (3) \qquad W(x)= x^m \cdot G(x) $

dla pewnej liczby całkowitej dodatniej $m$ i wielomianu $G(x)$ spełniającego warunek
$G(0) \neq 0$ . Na mocy (1) i (3) mamy

$ x^{5m} \cdot G(x^2) \cdot G(x^3)= W (x^2)\cdot W(x^3)=(W(x))^5 = x^{5m} \cdot (G(x))^5 , $

zatem dla dowolnej liczby rzeczywistej x zachodzi równość

$ G(x^2) \cdot G(x^3)=(G(x))^5. $

Innymi słowy, wielomian $G(x)$ również spełnia warunki zadania. Ponieważ $G(0)\neq 0$ , więc
z poprzedniej części rozwiązania wnioskujemy, że $G(x) \equiv 1$ . Wobec tego $W(x)= x$ .

Pozostaje już tylko zauważyć, że każdy taki wielomian $W(x)$ spełnia warunki zadania.

Odpowiedź: $W(x) \equiv 0$ , $W(x) \equiv 1$ oraz $W (x)= x^n$ dla $n =1,2,3,\dots$ .

LIX OM - I -Zadanie 7

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

W $n$ -osobowym stowarzyszeniu działa $2n-1$ komisji (każdy niepusty zbiór członków stowarzyszenia
tworzy komisję). W każdej komisji należy wybrać przewodniczącego. Wymagany jest przy tym warunek: Jeżeli
komisja $C$ jest sumą $C = A\cup B$ dwóch komisji $A$ i $B$ , to przewodniczący komisji $C$ jest też
przewodniczącym co najmniej jednej z komisji $A$ , $B$ . Wyznaczyć liczbę możliwych wyborów przewodniczących.

Rozwiązanie

Odpowiedź: n!.

Wskażemy wzajemnie jednoznaczną odpowiedniość między możliwymi wyborami przewodniczących komisji
a sposobami przydzielenia członkom stowarzyszenia numerów $1, 2, \dots , n$ (przy czym różnym członkom
przydzielone są różne numery). Tych ostatnich jest oczywiście tyle samo, ile permutacji zbioru $n$ -elementowego,
czyli $n!$ .

Przypuśćmy więc, że w każdej komisji wybrano przewodniczącego zgodnie z założeniami zadania.
Przypisujemy członkom stowarzyszenia numery indukcyjnie w następujący sposób:

Numer 1 otrzymuje przewodniczący komisji, w skład której wchodzą wszyscy członkowie stowarzyszenia.
Numer 2 otrzymuje przewodniczący komisji, w skład której wchodzą wszyscy członkowie stowarzyszenia oprócz członka o numerze 1.
Numer 3 otrzymuje przewodniczący komisji, w skład której wchodzą wszyscy członkowie stowarzyszenia oprócz członków o numerach 1 i 2, itd.

Wykażemy, że przy takim sposobie przypisania numerów spełniony jest następujący warunek:

(*) Przewodniczącym dowolnej komisji jest ten spośród jej członków, któremu przydzielony jest najmniejszy numer.

Rzeczywiście, rozpatrzmy dowolną komisję $A$ i niech $k$ będzie najmniejszym z numerów przypisanych członkom
tej komisji. Niech $B$ będzie komisją złożoną z wszystkich członków stowarzyszenia, którym przydzielono numery
nie mniejsze niż $k$ . Ze sposobu rozdzielenia numerów wynika, że przewodniczącym komisji $B$ jest członek
o numerze $k$ . Ponadto komisja $B$ jest sumą dwóch komisji: $A$ oraz $B\A$ . Ponieważ członek o numerze
$k$ nie należy do komisji $B\A$ , więc zgodnie z warunkami zadania musi on być przewodniczącym komisji A.

Określiliśmy więc odwzorowanie, które wyborowi przewodniczących komisji przyporządkowuje sposób przydzielenia
członkom stowarzyszenia liczb $1, 2, \dots , n$ . Aby dokończyć rozwiązanie zadania, wskażemy teraz odwzorowanie
odwrotne.

Mianowicie, jeżeli członkom stowarzyszenia przypisano liczby $1, 2, \dots , n$ , to w każdej komisji
wybieramy na przewodniczącego tego jej członka, który ma najmniejszy numer (warunek (*) będzie więc spełniony).
Jeżeli komisja $C$ jest sumą $C = A\cup B$ dwóch komisji $A, B$ i członek o numerze $k$ jest przewodniczącym
komisji $C$ , to należy on do jednej z komisji $A, B$ , w której jest członkiem o najniższym numerze — a więc jest
jej przewodniczącym. Widzimy zatem, że warunek dany w treści zadania jest spełniony. Wobec tego jeżeli
rozpoczniemy od wyborów przewodniczących komisji, przyporządkujemy członkom stowarzyszenia numery zgodnie
z określoną wcześniej zasadą, a następnie z tych numerów odtworzymy przewodniczących komisji, to
otrzymamy wyjściowy wybór przewodniczących. Podobnie jeżeli rozdzielimy numery członkom stowarzyszenia, na
ich podstawie wybierzemy przewodniczących komisji, a potem zgodnie z opisaną procedurą indukcyjną przypiszemy
członkom numery, to będą one tożsame z wyjściowymi numerami. W takim razie określone odwzorowania są wzajemnie
odwrotne, co kończy rozwiązanie.

LIX OM - I -Zadanie 8

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dany jest ostrosłup czworokątny $ABCDS$ o podstawie czworokąta wypukłego $ABCD$ . Sfera wpisana w ten
ostrosłup jest styczna do ściany $ABCD$ w punkcie $P$ . Dowieść, że

$ \measuredangle APB + \measuredangle CPD = 180^{\circ}. $

Rozwiązanie

Sposób I

Oznaczmy przez $K, L, M, N$ punkty styczności rozpatrywanej sfery odpowiednio ze ścianami
$SDA, SAB, SBC, SCD$ . Niech ponadto $K', L', M', N'$ będą odpowiednio punktami przecięcia prostych
$SK, SL, SM, SN$ z płaszczyzną $ABCD$ .

Z równości $KS = SL$ oraz $AK = AL$ wynika, że trójkąty $AKS$ i $ALS$ są przystające. A zatem

$ (1)\qquad \measuredangle AKK' = 180^{\circ} -\measuredangle AKS = 180^{\circ} -\measuredangle ALS = \measuredangle ALL' . $

Z kolei z równości $K'K = K'P$ oraz $AK = AP$ wynika, że trójkąty $AKK'$ oraz $APK$ są przystające.
Wobec tego $\measuredangle AKK' = \measuredangle APK'$ . Analogicznie dowodzimy, że $\measuredangle ALL' = \measuredangle APL'$ .

Łącząc ostatnie dwie równości z zależnością (1) uzyskujemy

$ \measuredangle APK' = \measuredangle APL' = \alpha. $

Rozumując podobnie dostajemy (rys. 2)

$ \measuredangle BPL' = \measuredangle BPM' = \beta,\quad \measuredangle CPM' = \measuredangle CPN' = \gamma, \quad \measuredangle DPN' = \measuredangle DPK' = \delta. $

Wobec tego

$ 2\alpha +2\beta +2\gamma +2\delta = \measuredangle K'PL' +\measuredangle L'PM' +\measuredangle M'PN' +\measuredangle N'PK' = 360^{\circ}, $

czyli $\alpha+\beta +\gamma +\delta = 180^{\circ}$ . Pozostało zauważyć, że

$ \measuredangle APB +\measuredangle CPD =(\alpha +\beta )+(\gamma + \delta) = 180^{\circ}, $

co kończy rozwiązanie zadania.

Sposób II

Poprowadźmy przez punkt $S$ wszystkie proste, które są styczne do danej sfery $s$ . Proste te wyznaczają
stożek $t$ , w który wpisana jest sfera $s$ . Część wspólna stożka $t$ oraz płaszczyzny $ABCD$ jest elipsą
$e$ wpisaną w czworokąt $ABCD$ , której jednym z ognisk jest punkt $P$ (zob. Szkoła geometrii. Odczyty
kaliskie — praca zbiorowa, Warszawa 1993).

Oznaczmy przez $K, L, M, N$ punkty styczności elipsy $e$ odpowiednio z bokami $DA, AB, BC, CD$ (rys. 3).
Wówczas (zob. LI Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Warszawa 2001, Dodatek B, str. 107, twierdzenie 3) otrzymujemy zależności

$ \measuredangle APK = \measuredangle APL, \quad \measuredangle BPL = \measuredangle BPM, \quad \measuredangle CPM = \measuredangle CPN, \quad \measuredangle DPN = \measuredangle DPK, $

z których analogicznie jak w sposobie I wynika teza zadania.

LIX OM - I -Zadanie 9

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Wyznaczyć najmniejszą liczbę rzeczywistą a o następującej własności:

Dla dowolnych liczb rzeczywistych $x, y, z \geqslant a$ spełniających warunek $x +y + z = 3$
prawdziwa jest nierówność

$ x^3 + y^3 + z^3 \geqslant 3. $

Rozwiązanie

Odpowiedź: $a = -5$ .

W rozwiązaniu wykorzystamy następującą tożsamość:

$ (1)\qquad t^3 +2\cdot \left(\frac{3-t}{2}\right)^3 - 3= \frac{3(t+5)(t-1)^2}{4} . $

Przypuśćmy, że liczba $a \leqslant 1$ ma daną w treści zadania własność. Liczby
$x = a, y = z = 2\cdot (\frac{3-a}{2})$ spełniają warunki $x, y, z \geqslant a$ i $x+y+z = 3$ , zatem

$ 0\leqslant x^3 + y^3 + z^3 - 3 = a^3 +2\cdot \left(\frac{3-a}{2}\right)^3 - 3= \frac{3(a+5)(a-1)^2}{4} $

na mocy (1), skąd wynika nierówność $a \geqslant -5$ .

Wykażemy z kolei, że liczba $a = -5$ spełnia warunki zadania. W tym celu rozpatrzmy takie liczby
$x, y, z \geqslant-5$ , że $x + y + z = 3$ . Bez ograniczenia ogólności przyjmijmy, że
$x \leqslant y \leqslant z$ . Suma $y + z$ jest liczbą dodatnią, gdyż w przeciwnym razie wobec
$y\leqslant z$ mielibyśmy $x \leqslant y \leqslant 0$ , skąd wynikałoby, że $x +y + z \leqslant y + z \leqslant 0$ ,
co przeczy warunkowi $x+y+z = 3$ . Skoro zaś $y + z> 0$ , prawdziwa jest nierówność

$ y^3 + z^3 - 2\left( \frac{y+z}{2}\right)^3 = \frac{3(y^3-y^2z-yz^2+z^3)}{4} = \frac{3(y-z)^2(y+z)}{4}\geqslant 0. $

skąd na podstawie tożsamości (1) otrzymujemy ostatecznie

$ x^3 + y^3 + z^3 \geqslant x^3 + 2\left(\frac{y+z}{2}\right)^3 = x^3 +2\cdot \left(\frac{3-x}{2}\right)^3 = 3 + \frac{3(x+5)(x-1)^2}{4} \geqslant 3. $

LIX OM - I -Zadanie 10

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dana jest liczba pierwsza p. Ciąg liczb całkowitych dodatnich $a_1, a_2, a_3, \dots$ spełnia warunek

$ (1) \qquad a_{n+1} = a_n +p\left[ \sqrt[p]{a_n} \right]\quad \text{dla } n =1, 2,3,\dots. $

Wykazać, że pewien wyraz tego ciągu jest $p$ -tą potęgą liczby całkowitej.
(Uwaga: Symbol $[x]$ oznacza największą liczbę całkowitą nie przekraczającą $x$ .)

Rozwiązanie

Zdefiniujmy ciągi liczb całkowitych nieujemnych $b_1, b_2, b_3, \dots$ oraz $r_1, r_2, r_3, \dots$
w następujący sposób:

$ b_n^p \leqslant a_n < (b_n + 1)^p \quad \text{ oraz } \quad r_n = a_n -b_^p $

dla $n =1,2,3,\dots$ . Inaczej mówiąc, $r_n$ jest różnicą między wyrazem an a największą nie
przekraczającą tego wyrazu $p$ -tą potęgą liczby całkowitej. Warunek (1) przepisujemy teraz w postaci

$ (2) \qquad a_{n+1} = a_n +pb_n. $

Zauważmy, ze jeżeli $r_n = 0$ , to $a_n = b_n^p$ jest $p$ -tą potęgą liczby całkowitej. Zadanie będzie
więc rozwiązane, jeśli udowodnimy, że $r_n = 0$ dla pewnej wartości $n$ .

Przypuśćmy, że wszystkie wyrazy ciągu $r_1, r_2, r_3, \dots$ są liczbami całkowitymi dodatnimi. Niech
$r_m$ będzie najmniejszym wśród tych wyrazów. Mamy więc $a_m = b_m^p +rm$ . Ponadto
$b_{m-1} <b_m$ , gdyż w przeciwnym razie mielibyśmy

$ r_{m-1} = a_{m-1} -b^p_{m-1} < a_m -b^p_{m-1} = r_m $

wbrew określeniu $m$ . Zauważmy dalej, że $a_{m-1} <(b_{m-1}+1)^p \leqslant b^p_m \leqslant a_m$
i wobec tego zachodzi nierówność

$ (3)\qquad r_m = a_m -b_m^p <am -a_{m-1} = pb_{m-1} < pb_m. $

Niech ponadto $k>m$ będzie najmniejszym wskaźnikiem, dla którego $b_k >b_m$ . Wówczas
$b_m = b_{m+1} = \dots = b_{k-1}$ , więc na mocy (2) otrzymujemy

$ \begin{split} a_{m+1} &= a_m +pb_m, \\ a_{m+2} &= a_{m+1} +pb_m, \\ \dots \\ a_k &= a_{k-1} +pb_m \end{split} $

i sumując stronami dochodzimy do wniosku, że

$ (4) \qquad a_k = a_m +pb_m(m -k)= b^p_m +pb_m(m-k)+r_m. $

Wykażemy z kolei, że $b_k = b_m +1$ . Istotnie, gdyby zachodziła nierówność
$b_k \geqslant b_m +2= b_{k-1} +2$ , mielibyśmy $a_{k-1} < (b_{k-1} +1)^p$ , $a_k \geqslant (b_{k-1} +2)^p$
oraz

$ (5) \qquad pb_{k-1} = a_k -a_{k-1} > (b_{k-1} +2)^p -(b_{k-1} +1)^p, $

ale pisząc $x = b_{k-1} +2$ , $y = b_{k-1} +1$ mamy $x-y =1$ , $x>y>b_{k-1}$ i widzimy, że

$ x^p-y^p=(x-y)(x^{p-1} + x^{p-2}y +\dots +y^{p-1}) > 1\cdot py^{p-1} > pb^{p-1}_{k-1} \geqslant pb_{k-1}. $

Nierówność (5) jest więc fałszywa, co dowodzi równości $b_k = b_m +1$ .

Na mocy (4) możemy zatem napisać

$ (b_m +1)^p +r_k = b^p_k +r_k = a_k = b^p_m +pb_m(m-k)+r_m, $

czyli

$ (6) \qquad r_m -r_k=(b_m+1)^p -b^p_m -pb_m(m-k). $

Ze wzoru dwumianowego otrzymujemy

$ (b_m +1)^p - b_m^p = \binom{p}{1} b^{p-1}_m + \binom{p}{2}b^{p-2}_m + \dots + \binom{p}{p-1} b_m +1 $

Ponieważ $p$ jest liczbą pierwszą, więc współczynniki dwumianowe $\binom{p}{i}$ są dla $i =1,2,\dots ,p - 1$
liczbami podzielnymi przez $p$ . Zatem liczba $(b_m + 1)^p - b_m^p$ daje resztę 1 z dzielenia przez
$pb_m$ . Wobec tego z (6) wynika, że liczba $r_m -r_k$ daje resztę 1 z dzielenia przez $pb_m$ .

W (3) uzyskaliśmy nierówność $r_m <pb_{m-1}$ korzystając jedynie z tego, że
$b_{m-1} <b_m$ . Analogicznie wyprowadzamy z nierówności $b_{k-1} <b_k$ , że $r_k <pb_m$ .
Liczby $r_m$ i $r_k$ należą więc do przedziału $(0; pb_m)$ , a różnica $r_m-r_k$ daje resztę 1 z dzielenia
przez $pb_m$ . Wynika stąd, że $r_k = r_m -1$ , co przeczy założeniu, że $r_m$ jest najmniejszym wyrazem
w ciągu $r_1, r_2, r_3, \dots$ .

To oznacza, że $r_n = 0$ dla pewnego wskaźnika $n$ , skąd wynika teza.

LIX OM - I -Zadanie 11

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Punkty $P_1, P_2, P_3, P_4, P_5, P_6, P_7$ leżą odpowiednio na bokach $BC, CA, AB, BC, CA, AB, BC$
trójkąta $ABC$ , przy czym spełnione są równości

$ \measuredangle P_1P_2C =\measuredangle AP_2P_3 =\measuredangle P_3P_4B =\measuredangle CP_4P_5 =\measuredangle P_5P_6A=\measuredangle BP_6P_7 =60^{\circ}. $

Dowieść, że $P_1 = P_7$ .

Rozwiązanie

Niech o będzie okręgiem opisanym na trójkącie $P_1P_2P_3$ .

Z warunków zadania wynika równość $\measuredangle P_1P_2P_3 = 60^{\circ}$ . To w połączeniu z równością
$\measuredangle P_3P_4B =60^{\circ}$ . dowodzi, że punkt $P_4$ leży na okręgu o, niezależnie od tego, czy leży
on na odcinku $P_1C$ (rys. 4), czy na odcinku $P_1B$ (rys. 5). Zauważmy ponadto, iż równość $P_1 = P_4$
zachodzi jedynie wtedy, gdy okrąg o jest styczny do boku $BC$ .

Dalej, na mocy założeń zadania mamy $\measuredangle P_5P_4P_3 = 60^{\circ}$ i $\measuredangle AP_2P_3 = 60^{\circ}$ ,
skąd wnioskujemy, że punkt $P_5$ leży na okręgu $o$ , zarówno wtedy, gdy punkt $P_5$ leży na odcinku $P_2C$
(rys. 6), jak i wtedy, gdy leży on na odcinku $P_2A$ (rys. 7). Tak jak poprzednio, równość $P_2 =P_5$
oznacza, że okrąg o jest styczny do boku $CA$ .

Analogicznie dowodzimy, że punkty $P_6$ i $P_7$ leżą na okręgu $o$ . Wynika stąd, że punkty $P_1, P_4, P_7$
leżą jednocześnie na okręgu $o$ i na boku $BC$ . Jeżeli okrąg ten jest styczny do danego boku, to oczywiście
$P_1 = P_4 = P_7$ . Jeżeli natomiast okrąg o przecina bok $BC$ w dwóch różnych punktach, to z przeprowadzonego
rozumowania otrzymujemy $P_1 \neq P_4$ i $P_4 \neq P_7$ , zatem równość $P_1 = P_7$ także jest spełniona.

LIX OM - I -Zadanie 12

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dana jest liczba całkowita $m \geqslant 2$ . Wyznaczyć najmniejszą taką liczbę całkowitą
$n \geqslant m$ , że dla każdego rozbicia zbioru $\{m,m+1,\dots ,n\}$ na dwa podzbiory, przynajmniej jeden z
tych podzbiorów zawiera takie liczby $a, b, c$ (niekoniecznie różne), że $ab = c$ .

Rozwiązanie

Odpowiedź: $n = m^5$ .

Załóżmy, że istnieje rozbicie zbioru $\{m,m+1,\dots ,m^5\}$ na dwa podzbiory $S$ i $T$ ,
z których żaden nie zawiera dwóch liczb (niekoniecznie różnych) wraz z ich iloczynem. Przypuśćmy przy tym,
że $m \in S$ . Liczba $m^2 = m \cdot m$ jest iloczynem dwóch elementów zbioru $S$ , zatem musimy mieć
$m^2 \in T$ . Stąd zaś $m^4= m^2\cdot m^2 \in S$ . Widzimy, że $m, m^4 \in S$ , co oznacza, że liczba
$m^5= m \cdot m^4$ należy do zbioru $T$ . Z drugiej strony, liczby $m, m^4$ są elementami zbioru $S$ ,
więc liczba $m^3$ nie może należeć do tego zbioru. Wobec tego $m, m^3, m^5 \in T$ .
Otrzymaliśmy zatem $m^2, m^3, m^5 \in T$ , czyli mamy sprzeczność.

Z drugiej strony, jeżeli podzielimy zbiór $\{m,m+1,\dots ,m^5 -1\}$ na następujące dwa podzbiory:

$ \begin{split} S &= \{m,m+1,\dots ,m^2 -2,m^2-1,m ,m^4 +1,\dots ,m^5 -2,m^5 -1\}, \\ T &= \{m^2 ,m^2 +1,\dots ,m^4 -2,m^4 -1\}, \end{split} $

to iloczyn dwóch elementów (niekoniecznie różnych) każdego z tych podzbiorów nie jest elementem tego
podzbioru. Rzeczywiście, do zbioru $T$ należą liczby nie mniejsze od $m^2$ , a więc iloczyn dowolnych dwóch
z nich jest równy co najmniej $m^4$ , zaś największym elementem tego zbioru jest liczba $m^4 -1$ . Z kolei do
zbioru $S$ należą liczby nie mniejsze od $m$ , więc iloczyn dowolnych dwóch jest równy co najmniej $m$ .
Iloczyn ten jest mniejszy od $m^4$ , jeżeli obie liczby są mniejsze od $m^2$ , albo jest równy przynajmniej
$m^5$ , jeżeli jedna z liczb wynosi co najmniej $m^4$ , i w obu przypadkach nie należy do zbioru $S$ .

Widzimy więc, że liczba $n = m^5 -1$ nie spełnia warunków zadania. Tym bardziej liczby
$n<m^5 - 1$ nie spełniają tych warunków, wystarczy bowiem z każdego ze zbiorów $S, T$ utworzonych dla wartości
$m^5 - 1$ usunąć liczby większe od $n$ . Wobec tego szukaną najmniejszą wartością jest $n = m^5$ .

LIX OM - II etap

II etap LIX Olimpiady Matematycznej

Załącznik	Wielkość
LIX OM II etap - Zadania [4]	60.31 KB
LIX OM II etap - Zadania z rozwiązaniami [5]	121.4 KB

LIX OM - II -Zadanie 1

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Wyznaczyć największą możliwą długość ciągu kolejnych liczb całkowitych, z których każdą można przedstawić w
postaci $x^3 +2y^2$ dla pewnych liczb całkowitych $x, y$ .

Rozwiązanie

Ciąg pięciu kolejnych liczb całkowitych -1, 0, 1, 2, 3 spełnia warunki zadania: istotnie, mamy

$ -1=(-1)^3 +2\cdot 0^2,\; 0=0^3 +2\cdot 0^2,\; 1=1^3 +2\cdot 0^2,\; 2=0^3 +2\cdot 1^2,\; 3=1^3 +2\cdot 1^2. $

Z drugiej strony, wśród dowolnych sześciu kolejnych liczb całkowitych istnieje liczba, powiedzmy
$m$ , która daje resztę 4 lub resztę 6 z dzielenia przez 8. Liczba $m$ jest parzysta; gdyby więc istniało przedstawienie
w postaci $m = x^3 +2y^2$ dla pewnych liczb całkowitych $x, y$ , to liczba $x$ byłaby parzysta. Wówczas jednak
uzyskalibyśmy podzielność $8|x^3$ i w efekcie liczby $m$ i $2y^2$ dawałyby tę samą resztę (4 lub 6) z dzielenia przez 8.
Wobec tego liczba $y^2$ dawałaby resztę 2 lub 3 z dzielenia przez 4. Jest to niemożliwe: równości

$ (2k)^2 =4\cdot k^2,\quad (2k +1)^2 =4\cdot (k^2 +k)+1 $

dowodzą, że kwadrat liczby całkowitej może dawać przy dzieleniu przez 4 tylko resztę 0 lub 1.

Wykazaliśmy tym samym, że wśród dowolnych sześciu kolejnych liczb całkowitych istnieje liczba, której nie da się przedstawić
w postaci $x^3 +2y^2$ .

Odpowiedź: Największa możliwa długość takiego ciągu wynosi 5.

LIX OM - II -Zadanie 2

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

W pięciokącie wypukłym $ABCDE$ spełnione są zależności

$ \measuredangle ABD &= \measuredangle ACE,& \measuredangle ACB &= \measuredangle ACD, \\ \measuredangle ADC &= \measuredangle ADE,& \measuredangle ADB &= \measuredangle AEC. $

Odcinki $BD$ i $CE$ przecinają się w punkcie $S$ . Dowieść, że proste $AS$ i $CD$ są prostopadłe.

Rozwiązanie

Z równości

$ \measuredangle ABD = \measuredangle ACE oraz \measuredangle ADB = \measuredangle AEC $

wynika (rys. 1), że trójkąty $BAD$ i $CAE$ są podobne (cecha kąt-kąt-kąt). Podobieństwo tych trójkątów
pozwala wnioskować, że

$ \measuredangle BAC = \measuredangle DAE \text{ oraz } \frac{BA}{DA}= \frac{CA}{EA} $

Zależności te dowodzą, że trójkąty $BAC$ i $DAE$ są podobne (cecha bok-kąt-bok). W konsekwencji otrzymujemy

$ (1) \qquad \measuredangle ABC = \measuredangle ADE = \measuredangle ADC. $

Ponadto prawdziwa jest zależność

$ \measuredangle ACB = \measuredangle ACD $

która w połączeniu z równością (1) implikuje, że trójkąty $ABC$ i $ADC$ są podobne (cecha kąt-kąt-kąt).
Mają one jednak wspólny odpowiedni bok $AC$ . Wobec tego trójkąty te są przystające i symetryczne względem prostej $AC$ .
Stąd wniosek, że proste $AC$ i $BD$ są prostopadłe.

Analogicznie dowodzimy, że proste $AD$ i $CE$ są prostopadłe. Zatem $S$ jest punktem przecięcia wysokości trójkąta
$CAD$ . To oznacza, że prosta $AS$ zawiera trzecią wysokość tego trójkąta, czyli jest prostopadła do prostej $CD$ .

LIX OM - II -Zadanie 3

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Wyznaczyć wszystkie takie funkcje $f$ , określone na zbiorze wszystkich liczb rzeczywistych i przyjmujące
wartości rzeczywiste, że dla dowolnych liczb rzeczywistych $x$ i $y$ zachodzi równość

$ (1)\qquad f(f(x)-y)= f(x)+f(f(y)-f(-x))+x. $

Rozwiązanie

Oznaczmy $c = f(0)$ . Podstawiając $x = y = 0$ w równości (1) otrzymujemy zależność $f(c)= f(f(0)) = 2f(0) = 2c$ . Następnie
kładąc $x =0$ i $y = c$ stwierdzamy, że

$ c = f(0) = f(0)+f(f(c)-c)+0 = c +f(2c-c)= c+f(c)=3c. $

Wynika stąd, że $c = 0$ , czyli $f(0) = 0$ .

Przyjmując teraz w warunku (1) wartość $x = 0$ widzimy, że

$ (2) \qquad f(-y)= f(f(y)) \text{ dla każdej liczby rzeczywistej } y. $

Podstawmy z kolei $y = f(x)$ w równości (1). Wówczas na mocy własności (2) dla dowolnej wartości $x$ dostajemy zależność

$ \begin{split} 0 &= f(0) = f(f(x)-f(x)) = f(x)+f(f(f(x))-f(-x))+x = \\ &= f(x)+f(f(-x)-f(-x))+x = f(x)+f(0)+x = f(x)+x. \end{split} $

Stąd $f(x)=-x$ dla każdej liczby rzeczywistej $x$ i pozostaje bezpośrednio sprawdzić, że funkcja dana tym wzorem
istotnie ma żądane własności.

Odpowiedź: Jedyną funkcją spełniającą warunki zadania jest $f(x)= -x$ .

LIX OM - II -Zadanie 4

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

W każdym polu kwadratowej tablicy o rozmiarach $n \times n$ napisana jest liczba całkowita. Możemy wielokrotnie
wykonywać następującą operację: Wybieramy dowolne pole tabeli i zmniejszamy wpisaną weń liczbę o liczbę pól sąsiednich
(mających wspólny bok z wybranym polem), zaś każdą z liczb wpisanych w pola sąsiednie zwiększamy o 1.

Dla każdej liczby całkowitej $n \geqslant 2$ rozstrzygnąć, czy z dowolnej początkowej tabeli, w której suma wszystkich
$n^2$ liczb jest równa zeru, można otrzymać tabelę składającą się z samych zer.

Rozwiązanie

Niech $P$ oznacza przekątną tabeli łączącą jej lewy górny róg z prawym dolnym rogiem. Udowodnimy, że w wyniku
wykonania opisanej operacji nie zmienia się parzystość sumy liczb znajdujących się na przekątnej $P$ (na rys. 2 pola
leżące na przekątnej $P$ są zacieniowane).

Dla każdego pola na przekątnej $P$ liczba pól sąsiednich wynosi 2 albo 4 i żadne z nich nie leży na przekątnej $P$ .
Każde pole sąsiadujące z przekątną $P$ (na rys. 2 takie pola oznaczone są krzyżykami) sąsiaduje z dokładnie dwoma polami
leżącymi na przekątnej $P$ . Pozostałe pola tabeli nie leżą na przekątnej $P$ i z nią nie sąsiadują. Jeżeli więc suma liczb
na przekątnej $P$ przed wykonaniem operacji wynosiła $s$ , to w wyniku jej wykonania suma ta będzie równa $s-4$ , $s-2$ , $s$ lub
$s+2$ , czyli jej parzystość nie zmieni się.

Zatem jeśli na początku wpiszemy do tabeli liczbę 1 w lewym górnym rogu, liczbę -1 w polu leżącym w prawym górnym rogu
oraz liczbę 0 w każde z pozostałych pól, to suma wszystkich liczb w tabeli będzie równa zeru, ale po wykonaniu dowolnej
ilości operacji suma liczb leżących na przekątnej $P$ będzie nieparzysta. Wobec tego nie jest możliwe, by przekątna $P$ ,
a tym bardziej — cała tabela, składała się z samych zer.

Odpowiedź: Dla każdego $n \geqslant 2$ istnieje początkowa tabela o sumie liczb równej zeru, z której nie można
otrzymać tabeli złożonej z samych zer.

LIX OM - II -Zadanie 5

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dany jest trójkąt $ABC$ , w którym $AC = BC$ . Punkt $D$ leży na boku $AB$ tego trójkąta, przy czym $AD < BD$ . Punkt
$E$ jest symetryczny do punktu $A$ względem prostej $CD$ . Wykazać, że

$ \frac{AC}{CD} = \frac{BE}{BD-AD} $

Rozwiązanie

Oznaczmy przez $F$ punkt symetryczny do $A$ względem punktu $D$ (rys. 3). Na mocy nierówności $AD <BD$ punkt $F$
znajduje się wewnątrz odcinka AB.

Ponieważ $AD = DF$ oraz punkty $A$ i $E$ są symetryczne względem prostej $CD$ , więc stosując twierdzenie odwrotne do
twierdzenia Talesa stwierdzamy, że $CD || FE$ . Stąd w szczególności wynika, że proste $CD$ i $BE$ nie są równoległe,
zatem przecinają się one w pewnym punkcie $G$ . Ponadto

$ (1) \qquad \measuredangle BFE = \measuredangle BDG = \measuredangle CDA. $

Dalej, zauważmy, że $CA = CB = CE$ , punkty $A$ , $B$ i $E$ leżą więc na okręgu o środku w punkcie $C$ . Wobec tego otrzymujemy

$ (2) \qquad \measuredangle ABE = \measuredangle ACE = \measuredangle ACD. $

Łącząc równości (1) i (2) dochodzimy do wniosku, że trójkąty $ACD$ i $EBF$ są podobne (cecha kąt-kąt-kąt). Zatem

$ \frac{AC}{CD}=\frac{BE}{BF}=\frac{BE}{BD-AD} $

LIX OM - II -Zadanie 6

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dana jest liczba całkowita dodatnia $n$ niepodzielna przez 3. Udowodnić, że istnieje liczba $m$ o następującej własności:
Każda liczba całkowita nie mniejsza niż $m$ jest sumą cyfr pewnej wielokrotności liczby $n$ .

Rozwiązanie

Przez liczbę dobrą będziemy rozumieć taką liczbę całkowitą dodatnią, która jest sumą cyfr pewnej wielokrotności liczby $n$ .

Zauważmy przede wszystkim, że suma dwóch liczb dobrych jest również liczbą dobrą. Rzeczywiście, niech $k_1, k_2$ będą
wielokrotnościami liczby $n$ o sumach cyfr odpowiednio równych $s_1, s_2$ . Niech $t$ będzie taką liczbą całkowitą, że
$10^t >k_2$ . Wówczas liczba $k = 10^t \cdot k_1 +k_2$ jest wielokrotnością liczby $n$ , zaś suma cyfr liczby $k$ jest równa
$s_1 +s_2$ , gdyż przy dodawaniu liczb $10^t \cdot k_1$ i $k_2$ niezerowe cyfry występują na różnych pozycjach.

Liczba $n$ nie jest podzielna przez 3, zatem jej suma cyfr a także nie jest podzielna przez 3.

Niech teraz $b$ będzie taką liczbą całkowitą, że $10^{3^b} >n$ . Przyjmijmy, że kolejnymi cyframi zapisu dziesiętnego
liczby $n$ są cyfry $c_1, c_2, \dots , c_l$ . Możemy oczywiście przyjąć, że $c_l \neq 0$ , gdyż podzielenie liczby
$n$ przez 10 nie zmienia warunków zadania. Wówczas kolejnymi cyframi zapisu dziesiętnego liczby
$(10^{3^b} -1)n = \underbrace{999\dots 99}_{3^b} \cdot n$ , podzielnej przez n, są cyfry:

$ c_1,c_2, \dots , c_l-1,c_l -1, \underbrace{9, 9, \dots , 9, 9}_{3^b-l}, 9-c_1, 9-c_2, \dots , 9-c_{l-1}, 10-c_l. $

Stąd wynika, że suma cyfr liczby $(10^{3^b} -1)n$ wynosi $9\cdot 3^b = 3^{b+2}$

Udowodniliśmy zatem, iż liczbami dobrymi są: liczba $a$ , która nie jest podzielna przez 3, oraz liczba $3^d$ , gdzie $d = b+2$ .

Wykażemy, że każda liczba całkowita nie mniejsza niż $a \cdot 3^d$ jest dobra. Wyniknie stąd, że liczba
$m = a\cdot 3^d$ spełnia tezę zadania.

Niech więc $s \geqslant a\cdot 3^d$ będzie dowolną liczbą całkowitą. Liczby

$ (*) \qquad s, s-a, s -2a, \dots , s-(3^d -1)a $

są wówczas dodatnie. Ponadto żadne dwie z nich nie dają tej samej reszty z dzielenia przez $3^d$ (gdyż podzielność
$3^d |(s - ia) - (s - ja)=(j - i)a$ przy pewnych wskaźnikach $0 \leqslant i,j \leqslant 3^d -1$ ze względu na niepodzielność
liczby a przez 3 jest możliwa tylko wtedy, gdy $3^d |j-i$ , co jednak pociąga $i=j$ ). Liczb wypisanych w ciągu (*) jest
$3d$ , istnieje więc wśród nich liczba, która jest podzielna przez $3^d$ . Niech na przykład $s-va = w \cdot 3^d$ . Wówczas
$v,w \geqslant 0$ oraz

$ s = \underbrace{a+a+ \dots +a}_{v}+\underbrace{3^d +3^d +\dots +3^d}_{w}. $

Liczby $a$ i $3^d$ są dobre. Zatem z powyższego przedstawienia wnioskujemy, że liczba $s$ jako suma liczb dobrych również jest
dobra, a tego dowodziliśmy.

LIX OM - III etap

III etap LIX Olimpiady Matematycznej

Załącznik	Wielkość
LIX OM III etap - Zadania [6]	68.08 KB
LIX OM III etap - Zadania z rozwiązaniami [7]	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.