LII OM

LII Olimpiada Matematyczna

LII OM - I etap

I etap LII Olimpiady Matematycznej

Załącznik	Wielkość
LII OM I etap - Zadania [1]	69.01 KB
LII OM I etap - Zadania z rozwiązaniami [2]	105.94 KB

LII OM - I - Zadanie 1

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Rozwiązać w liczbach całkowitych równanie

$ x^{2000} + 2000^{1999} = x^{1999} + 2000^{2000}. $

Rozwiązanie

Dane równanie sprowadzamy do postaci $f (x) = f (2000)$ , gdzie

$ f (x)=x^{2000} - x^{1999} = (x - 1)x^{1999}. $

Ponieważ $f$ jest funkcją rosnącą na przedziale $\langle 1,\infty )$ , więc dane równanie ma w tym przedziale tylko jedno rozwiązanie, którym jest $x = 2000$ . Na zbiorze $(-\infty,0\rangle$ funkcja $f$ jest malejąca, więc istnieje co najwyżej jedna liczba całkowita ujemna $a$ , dla której $f (a) = f (2000)$ . Jednakże

$ f (-1999) = 2000 \cdot 1999^{1999} < 1999 \cdot 2000^{1999} = f (2000) = f (a) $

oraz

$ f (-2000) = 2001 \cdot 2000^{1999} > 1999 \cdot 2000^{1999} = f (2000) = f (a). $

Zatem $a \in (-2000,-1999)$ , co przeczy temu, że $a$ jest liczbą całkowitą.

Odpowiedź: Dane równanie ma jedno rozwiązanie w liczbach całkowitych: $x = 2000$ .

LII OM - I - Zadanie 2

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Punkty $D$ i $E$ leżą odpowiednio na bokach $BC$ i $AC$ trójkąta $ABC$ . Odcinki $AD$ i $BE$ przecinają się w punkcie $P$ . Punkty $K$ i $L$ leżą odpowiednio na bokach $BC$ i $AC$ , przy czym czworokąt $CLPK$ jest równoległobokiem. Dowieść, że

$ \frac{AE}{EL}=\frac{BD}{DK}. $

Rozwiązanie

Ponieważ $KD \parallel LP$ , $DP \parallel PA$ oraz $PK \parallel AL$ , więc trójkąty $KDP$ i $LPA$ są podobne (rys. 1). Zatem

$ \frac{DK}{PL}=\frac{PK}{AL},\ \textrm{czyli}\ AL\cdot DK=PK \cdot PL. $

Analogicznie, korzystając z podobieństwa trójkątów $LEP$ i $KPB$ dowodzimy, że $BK \cdot EL = PL \cdot PK$ . Na mocy dwóch ostatnich równości otrzymujemy

$ AL\cdot DK=BK \cdot EL,\ \textrm{czyli}\ \frac{AL}{EL}=\frac{BK}{DK}. $

Stąd

$ \frac{AE+EL}{EL}=\frac{BD+DK}{DK},\ \text{a więc}\ \frac{AE}{EL}=\frac{BD}{DK}. $

LII OM - I - Zadanie 3

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Znaleźć wszystkie takie liczby naturalne $n \geq 2$ , że nierówność

$ (1) \qquad x_1x_2+x_2x_3+\ldots+x_{n-1}x_{n}\leq\frac{n-1}{n}(x_{1}^{2}+x_{2}^{2}+\ldots+x_{n}^{2}) $

zachodzi dla dowolnych liczb rzeczywistych dodatnich $x_1,x_2,\ldots,x_n$ .

Rozwiązanie

Odpowiedź: Jedyną liczbą spełniającą warunki zadania jest $n = 2$ .

Dla $n = 2$ dana nierówność przyjmuje postać

$ x_{1}x_{2}\leq\frac{1}{2}(x_{1}^{2}+x_{2}^{2}),\quad \textrm{co sprowadza się do}\quad 0\leq\frac{1}{2}(x_{1}-x_{2})^{2}. $

Zatem liczba $n = 2$ spełnia warunki zadania.

Jeśli $n \geq 3$ , to nierówność (1) nie jest prawdziwa dla dowolnych liczb rzeczywistych dodatnich. Liczby

$ (2) \qquad x_1 = 3,\ x_2 = x_3 = \ldots = x_{n-1} = 4,\ x_n = 3 $

stanowią kontrprzykład. Istotnie: wstawiając powyższe wartości do nierówności (1) uzyskujemy

$ 12+\underbrace{16+16+\ldots+16}_{n-3} +12\leq \frac{n-1}{n}(9+ \underbrace{16+16+\ldots+16}_{n-2} +9). $

Przekształcając równoważnie powyższą nierówność otrzymujemy $3n \leq 7$ , co nie jest prawdą, gdy $n \geq 3$ .

LII OM - I - Zadanie 4

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Rozstrzygnąć, czy w sześciennym pudełku o krawędzi 4 można umieścić 65 kul o średnicy 1.

Rozwiązanie

Odpowiedź: Można.

Sposób umieszczenia kul jest następujący.

Na dnie pudełka umieszczamy warstwę złożoną z 16 kul. Następnie kładziemy warstwę złożoną z 9 kul, z których każda jest styczna do czterech kul pierwszej warstwy (rys. 1 i 2). Trzecia warstwa składa się z $16$ kul stycznych do kul drugiej warstwy (rys. 4 i 5). Podobnie umieszczamy dwie następne warstwy (rys. 6).

Łącznie umieściliśmy więc $16 + 9 +16+ 9 + 16 = 66$ kul. Pozostaje obliczyć, jak wysoko sięga piąta warstwa.

Wybierzmy dowolną kulę drugiej warstwy; kula ta jest styczna do czterech kul pierwszej warstwy. Środki tych pięciu kul są wierzchołkami ostrosłupa prawidłowego czworokątnego, którego każda krawędź ma długość 1 (rys. 3). Na mocy twierdzenia Pitagorasa wysokość tego ostrosłupa wynosi $\frac{\sqrt{2}}{2}$ . Stąd wynika, że najwyższy punkt, do którego sięga piąta warstwa, jest odległy od płaszczyzny podstawy o $\frac{1}{2}+4\cdot\frac{\sqrt{2}}{2}+\frac{1}{2}=1+2\sqrt{2}<4$ . Umieszczone w ten sposób 66 kul mieści się w sześciennym pudełku o krawędzi 4.

LII OM - I - Zadanie 5

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Dowieść, że dla dowolnej liczby naturalnej $n \geq 2$ i dowolnej liczby pierwszej $p$ liczba $n^{p^p} + p^p$ jest złożona.

Rozwiązanie

Jeżeli $p$ jest liczbą pierwszą nieparzystą, to na mocy tożsamości

$ (1) \qquad x^{p}+y^{p}=(x+y)(x^{p-1}-x^{p-2}y+x^{p-3}y^{2}-\ldots-xy^{p-2}+y^{p-1}), $

w której kładziemy $x = n^{p^{p-1}}$ i $y = p$ , liczba $n^{p^p} + p^p$ jest złożona. (Dla powyższych wartości $x$ , $y$ zachodzą nierówności $x^p + y^p >x + y> 1$ , więc każdy z czynników stojących po prawej stronie wzoru (1) jest większy od 1).

Natomiast dla $p = 2$ otrzymujemy $n^4 + 4 = (n^2 + 2n + 2)(n^2 - 2n + 2)$ . Ponieważ $n \geq 2$ , więc oba czynniki są większe od $1$ . Stąd wynika, że dla $n \geq 2$ liczba $n^4 + 4$ jest złożona.

LII OM - I - Zadanie 6

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Liczby całkowite $a$ , $b$ , $x$ , $y$ spełniają równanie

$ a+b\sqrt{2001}=(x+y\sqrt{2001})^{2000} $

Udowodnić, że $a \geq 44b$ .

Rozwiązanie

Wykażemy najpierw, że zachodzi następująca równość:

$ (1) \qquad a-b\sqrt{2001}=(x-y\sqrt{2001})^{2000}. $

Istotnie: ze wzoru dwumianowego Newtona otrzymujemy

$ (x+y\sqrt{2001})^{2000}=\sum_{k=0}^{2000}{{2000} \choose k} y^{k}2001^{k/2}x^{2000-k}=c+d\sqrt{2001}, $

gdzie liczby całkowite c, d są dane przez:

$ (2)\qquad c= \sum_{\ell=0}^{1000} {{2000} \choose {2\ell}} y^{2\ell}2001^{\ell}x^{2000-2\ell},\ d = \sum_{\ell=0}^{999} {{2000} \choose {2\ell+1}} y^{2\ell+1}2001^{\ell}x^{1999-2\ell}. $

Korzystając z danej w treści zadania równości uzyskujemy

$ (a-c)+(b-d)\sqrt{2001}=0. $

Z niewymierności liczby $\sqrt{2001}$ wynika, że $b = d$ , co z kolei pociąga za sobą $a = c$ . Zatem na mocy związków (2) otrzymujemy

$ \begin{split} a-b\sqrt{2001}&=c-d\sqrt{2001}=\\ &=\sum_{k=0}^{2000}{{2000} \choose k} (-y)^{k}2001^{k/2}x^{2000-k}=(x-y\sqrt{2001})^{2000}, \end{split} $

co dowodzi równości (1).

Z zależności (1) wynika, że $a \geq b\sqrt{2001}$ . Ponadto

$ 2a=(x+y\sqrt{2001})^{2000}+(x-y\sqrt{2001})^{2000}\geq 0. $

Jeżeli $b< 0$ , to nierówność podana w tezie zadania jest spełniona, gdyż $a \geq 0$ . Jeśli zaś $b \geq 0$ , to

$ a\geq b\sqrt{2001}\geq 44b. $

LII OM - I - Zadanie 7

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Dany jest trójkąt równoramienny $ABC$ o kącie prostym przy wierzchołku $A$ . Punkty $D$ i $E$ leżą na przeciwprostokątnej $BC$ , przy czym $\measuredangle DAE = 45^\circ$ . Okrąg opisany na trójkącie $ADE$ przecina boki $AB$ i $AC$ odpowiednio w punktach $P$ i $Q$ . Dowieść, że $BP + CQ = PQ$ .

Rozwiązanie

Punkty $A$ , $P$ , $E$ , $D$ leżąna jednym okręgu, więc $\measuredangle ADE = \measuredangle BPE$ (rys. 1). Ponadto $\measuredangle DAE = 45^\circ = \measuredangle PBE$ . Z powyższych równości wynika, że trójkąty $ADE$ i $BPE$ sąpodobne, skąd w szczególności

$ (1) \qquad \measuredangle AED = \measuredangle BEP. $

Analogicznie dowodzimy, że

$ (2) \qquad \measuredangle ADE = \measuredangle CDQ. $

Niech $A'$ , $P'$ , $Q'$ będą odpowiednio punktami symetrycznymi do $A$ , $P$ , $Q$ względem prostej $BC$ . Na mocy równości (1) punkty $A$ , $E$ , $P'$ są współliniowe; z równości (2) wynika, że punkty $A$ , $D$ , $Q'$ są współliniowe.

Pozostaje wykazać, że $BP' + CQ' = P'Q'$ , przy założeniu, że punkty $P'$ i $Q'$ leżą odpowiednio na bokach $BA'$ i $CA'$ kwadratu $ABA'C$ oraz spełniony jest warunek $\measuredangle P'AQ' =45^\circ$ (rys. 2).

Niech $K$ będzie punktem symetrycznym do punktu $B$ względem prostej $AP'$ . Wówczas

$ (3) \qquad AC = AK \ \textrm{oraz} \ \measuredangle AKP' = 90^\circ. $

Ponadto

$ \measuredangle CAQ' = 45^\circ - \measuredangle P'AB = 45^\circ - \measuredangle P'AK = \measuredangle KAQ'. $

Z ostatniej zależności oraz z pierwszej równości (3) wynika, że trójkąty $CAQ'$ i $KAQ'$ są przystające (cecha bok-kąt-bok).

Zatem $\measuredangle AKQ' = 90^\circ$ , co w połączeniu z drugą równością (3) dowodzi, że punkty $P'$ , $K$ , $Q'$ leżąna jednej prostej. Stąd $BP' + CQ' = KP' + KQ' = P'Q'$ , co należało wykazać.

LII OM - I - Zadanie 8

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Rozstrzygnąć, dla jakich par liczb naturalnych $m$ i $n$ prostokąt o bokach długości $m$ i $n$ można pociąć na części przystające do figury na rysunku. Każdy z czterech kwadratów na rysunku ma bok długości $1$ .

Rozwiązanie

Odpowiedź: Żądany podział jest możliwy wtedy i tylko wtedy, gdy $m,n > 1$ oraz iloczyn $mn$ jest podzielny przez $8$ .

Załóżmy najpierw, że udało nam się pociąć prostokąt $m \times n$ na części przystające do danej figury (które w dalszej części rozwiązania będziemy nazywać klockami). Oczywiście $m,n> 1$ . Wykażemy, że $8|mn$ .

Każdy klocek składa się z czterech kwadratów jednostkowych, zatem iloczyn $mn$ (pole prostokąta) musi być liczbą podzielną przez $4$ . Stąd w szczególności wynika, że długość jednego z boków prostokąta $m\times n$ jest liczbą parzystą. Przyjmijmy więc, bez straty ogólności, że szerokość prostokąta, np. wielkość $m$ , jest parzysta.

Podzielmy dany prostokąt na $mn$ kwadratów jednostkowych (które będziemy dalej nazywać kratkami). Wówczas prostokąt składa się z $m$ (a więc parzystej liczby) kolumn, z których każda zawiera $n$ kratek (rys. 1).

Pomalujmy kolumny prostokąta na przemian na czarno i biało (rys. 2). Każdy klocek wycięty z tak pomalowanego prostokąta zawiera trzy kratki jednego koloru i jedną kratkę drugiego koloru. Ponieważ liczba kratek białych danego prostokąta jest równa liczbie kratek czarnych, więc klocków zawierających trzy kratki białe musi być tyle samo, co klocków zawierających trzy kratki czarne. Liczba klocków, na które składa się cały prostokąt, jest więc parzysta, co oznacza, że iloczyn $mn$ jest podzielny przez $8$ .

Załóżmy teraz, że $m,n> 1$ oraz $8| mn$ . Wykażemy, że prostokąt $m \times n$ da się pociąć na klocki.

Zauważmy, że prostokąty $4\times 2$ oraz $8\times 3$ da się pociąć na klocki (rys. 3, 4). Zatem wystarczy wykazać, że prostokąt $m\times n$ da się pociąć na prostokąty $4\times 2$ oraz $8 \times 3$ .

Jeśli jedna z liczb $m$ , $n$ jest podzielna przez $4$ , a druga parzysta, to prostokąt $m \times n$ da się pociąć na prostokąty $4\times 2$ (rys. 5), bez konieczności używania prostokątów $8\times 3$ .

Pozostał do rozpatrzenia przypadek, w którym jedna z liczb $m$ , $n$ jest podzielna przez $8$ (bez straty ogólności przyjmijmy, że jest nią $m$ ), zaś druga (czyli $n$ ) jest nieparzysta i nie mniejsza niż $3$ . Prostokąt $m \times n$ dzielimy wówczas na dwa prostokąty $m \times (n-3)$ i $m \times 3$ , z których pierwszy dzielimy na prostokąty $4 \times 2$ , a drugi na prostokąty $8 \times 3$ (rys. 6). Zatem również i w tym przypadku żądany podział jest możliwy.

LII OM - I - Zadanie 9

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Dowieść, że wśród dowolnych $12$ kolejnych liczb całkowitych dodatnich istnieje liczba nie będąca sumą $10$ czwartych potęg liczb całkowitych.

Rozwiązanie

Liczba będąca czwartą potęgą liczby całkowitej daje z dzielenia przez $16$ resztę $0$ lub $1$ . Istotnie: dla liczb parzystych postaci $2k$ mamy $(2k)^4 = 16k^4$ , natomiast dla liczb nieparzystych 2k + 1 uzyskujemy

$ (2k+1)^{4}=16\left(k^{4}+2k^{3}+\frac{1}{2}k(3k+1)\right)+1. $

(Liczba $\frac{1}{2} k(3k+1)$ jest całkowita dla dowolnej liczby całkowitej $k$ ).

Stąd wynika, że liczba, która jest sumą $10$ czwartych potęg liczb całkowitych, daje z dzielenia przez $16$ jedną z jedenastu reszt: $0,1,2,3,\ldots, 10$ . Wśród $12$ kolejnych liczb całkowitych żadne dwie nie dają tej samej reszty z dzielenia przez $16$ . Zatem któraś z tych $12$ liczb nie daje z dzielenia przez $16$ reszty ze zbioru $\{0,1,2,3,\ldots,10\}$ . Ta liczba nie może być więc sumą $10$ czwartych potęg liczb całkowitych.

LII OM - I - Zadanie 10

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Dowieść, że wewnątrz dowolnego trójkąta $ABC$ istnieje punkt $P$ o następującej własności:

Każda prosta przechodząca przez punkt $P$ dzieli obwód trójkąta $ABC$ w takim samym stosunku, w jakim dzieli ona jego pole.

Rozwiązanie

Wykażemy, że własność opisaną w treści zadania ma środek okręgu wpisanego.

Niech $\ell$ będzie dowolną prostą przechodzącą przez punkt $P$ będący środkiem okręgu wpisanego w trójkąt $ABC$ (rys. 1). Bez straty ogólności przyjmijmy, że prosta $\ell$ przecina boki $AC$ i $BC$ odpowiednio w punktach $D$ i $E$ . Należy wykazać, że

$ (1) \qquad \frac{[ABED]}{[DEC]} =\frac{DA + AB + BE}{EC + CD}, $

gdzie $[\mathcal{F}]$ jest polem figury $\mathcal{F}$ . Oznaczając przez $r$ promień okręgu wpisanego w trójkąt $ABC$ otrzymujemy

$ \begin{split} (2)\qquad [ABED]&=[DAP]+[ABP]+[BEP]= \frac{1}{2}DA\cdot r+\frac{1}{2}AB\cdot r+\frac{1}{2}BE \cdot r=\\ &=\frac{1}{2}(DA+AB+BE)\cdot r \end{split} $

oraz

$ (3)\qquad [DEC]=[ECP]+[CDP]=\frac{1}{2}EC\cdot r+\frac{1}{2}CD\cdot r=\frac{1}{2}(EC+CD)\cdot r. $

Dzieląc stronami równości (2) i (3) uzyskujemy równość (1).

LII OM - I - Zadanie 11

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Układ liczb całkowitych dodatnich $c_1,c_2,\ldots,c_n$ nazwiemy dopuszczalnym, gdy za pomocą wagi szalkowej i dwóch kompletów odważników o ciężarach $c_1,c_2,\ldots,c_n$ można zważyć dowolny przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą $2(c_1 + c_2 +\ldots + c_n)$ . Dla każdej liczby $n$ wyznaczyć maksymalną sumę $n$ liczb tworzących układ dopuszczalny.

Uwaga: Odważniki można kłaść na obie szalki wagi.

Rozwiązanie

Niech $p_1,p_2,\ldots,p_n$ oraz $q_1,q_2,\ldots,q_n$ będą dwoma zestawami odważników o ciężarach odpowiednio $c_1,c_2,\ldots,c_n$ . Wykażemy najpierw, że za pomocą tych dwóch zestawów możemy zważyć co najwyżej $\frac{1}{2}(5^n-1)$ przedmiotów, niezależnie od tego, czy liczby $c_1,c_2,\ldots,c_n$ tworzą układ dopuszczalny, czy nie.

Ustawienie odważników na szalkach wagi nazwiemy optymalnym, jeśli dla każdego $k \in\{1,2,\ldots,n\}$ ciężarki $p_k$ i $q_k$ nie znajdują się na dwóch różnych szalkach wagi.

Aby otrzymać ustawienie optymalne, dwa odważniki $p_k$ i $q_k$ możemy ustawić na szalkach wagi na $5$ sposobów (zob. tabela obok). Zatem liczba wszystkich optymalnych ustawień odważników jest równa $5^n$ . W tej liczbie mieści się jedno ustawienie „puste", w którym na żadną szalkę nie kładziemy odważników. Pozostałe ustawienia można połączyć w pary symetryczne, w których jedno ustawienie powstaje z drugiego przez zamianę zawartości obydwu szalek wagi.

lewa szalka	prawa szalka
0	0
1	0
2	0
0	1
0	2

Tak więc liczba niepustych, istotnie różnych optymalnych ustawień odważników wynosi $\frac{1}{2}(5^n-1)$ , co oznacza, że możemy zważyć co najwyżej $\frac{1}{2}(5^n-1)$ przedmiotów o różnych ciężarach.

Załóżmy, że liczby $c_1,c_2,\ldots,c_n$ tworzą układ dopuszczalny. Wówczas masa najcięższego przedmiotu, jaki można zważyć, wynosi $2(c_1 + c_2 +\ldots + c_n)$ . Ponieważ nie da się zważyć więcej niż $\frac{1}{2}(5^n-1)$ przedmiotów,

$ (1)\qquad 2(c_{1}+c_{2}+\ldots+c_{n})\leq\frac{1}{2}(5^{n}-1). $

Wykażemy teraz, że liczby $c_1 = 1, c_2 = 5, c_3 = 5^2,\ldots ,c_n = 5^{n-1}$ tworzą układ dopuszczalny. Dla tych wartości $c_i$ zachodzi równość

$ (2)\qquad 2(c_{1}+c_{2}+\ldots+c_{n})=\frac{1}{2}(5^{n}-1). $

Należy więc udowodnić, że za pomocą dwóch kompletów odważników o ciężarach $1, 5, 5^2,\ldots,5^{n-1}$ można zważyć każdy przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą $\frac{1}{2}(5^n-1)$ . Dowód tego faktu przeprowadzimy na dwa sposoby.

Sposób I

Indukcja. Dla $n = 1$ mamy dwa odważniki o ciężarze $1$ każdy i za ich pomocą można zważyć przedmiot o ciężarze $1$ lub $2 = \frac{1}{2}(5^1 - 1)$ .

Załóżmy, że dysponujemy dwoma zestawami odważników o ciężarach $1, 5, 5^2 ,\ldots , 5^{n-1}$ i za ich pomocą umiemy zważyć każdy przedmiot o ciężarze nie przekraczającym $\frac{1}{2}(5^n-1)$ . Oto jak zważyć przedmiot $p$ o ciężarze $c$ , gdy:

(a) $c\in \langle \frac{1}{2}(5^n-1)+1 ,5^n-1 \rangle$ .

Korzystając z założenia indukcyjnego ważymy najpierw przedmiot $q$ o ciężarze $5^n-c$ kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie $5^n$ na prawą szalkę wagi, zdejmujemy przedmiot $q$ i kładziemy przedmiot $p$ na lewą szalkę.

(b) $c\in \langle 5^n+1,\frac{1}{2}(3\cdot 5^n-1)\rangle$ .

Podobnie jak w przypadku (a), ważymy najpierw przedmiot $q$ o ciężarze $c - 5^n$ kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie $5^n$ na lewą szalkę wagi, zdejmujemy przedmiot $q$ i kładziemy przedmiot $p$ na prawą szalkę.

Ważymy najpierw przedmiot $q$ o ciężarze $2\cdot 5^n - c$ kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie $5^n$ na prawą szalkę wagi, zdejmujemy przedmiot $q$ , po czym kładziemy przedmiot $p$ na lewą szalkę.

(d) $c\in \langle 2\cdot 5^n+1,\frac{1}{2}(5^{n+1}-1) \rangle$ .

Ważymy najpierw przedmiot $q$ o ciężarze $c - 2\cdot 5^n$ kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie $5^n$ na lewą szalkę wagi, zdejmujemy przedmiot $q$ , po czym kładziemy przedmiot $p$ na prawą szalkę.

Przedmioty o masach $5^n$ i $2\cdot 5^n$ można zważyć używając jedynie dwóch odważników o masie $5^n$ . Dowód indukcyjny został więc zakończony.

Sposób II

Niech $c$ będzie dowolną liczbą naturalną nie przekraczającą $\frac{1}{2}(5^n-1)$ . Wówczas liczba $c + \frac{1}{2}(5^n-1)$ jest mniejsza od $5^n$ . Liczbę tę można zatem zapisać w systemie piątkowym przy użyciu co najwyżej $n$ cyfr. Innymi słowy

$ c+\frac{1}{2}(5^{n}-1)=\sum_{i=0}^{n-1}a_{i}5^{i},\ \textrm{gdzie} \ a_{i}\in\{0,1,2,3,4\}. $

Ponieważ $\frac{1}{2}(5^{n}-1)=2(1+5+5^{2}+\ldots+5^{n-1})$ , więc

$ c=\sum_{i=0}^{n-1}\varepsilon_{i}5^{i},\ \textrm{gdzie}\ \varepsilon_{i}\in\{-2,-1,0,1,2\}. $

Powyższa równość oznacza, że przedmiot o ciężarze $c$ można zważyć za pomocą dwóch kompletów odważników o ciężarach $1, 5, 5^2, \ldots,5^{n-1}$ , co kończy dowód.

Z równości (1) i (2) wynika, że maksymalna suma zbioru $n$ liczb dopuszczalnych wynosi $\frac{1}{4}(5^n-1)$ .

LII OM - I - Zadanie 12

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Rozpatrujemy ciągi liczb całkowitych $x_0,x_1,\ldots,x_{2000}$ spełniające warunki

$ x_0 = 0\ \textrm{oraz}\ |x_n| = |x_{n-1} + 1| \ \textrm{dla}\ n = 1,2,\ldots,2000. $

Znaleźć najmniejszą wartość wyrażenia $|x_1 + x_2 +\ldots + x_{2000}|$ .

Rozwiązanie

Odpowiedź: Najmniejsza wartość danego wyrażenia wynosi $12$ .

Wykażemy indukcyjnie, że dla dowolnego ciągu $(x_n)$ spełniającego warunki zadania zachodzi równość

$ (1)\qquad x_0 + x_1 + x_2 + \ldots + x_n = \frac{1}{2} (x_n^2 + 2x_n-n) \quad (n = 0,1,2,3,\ldots,2000). $

Dla $n = 0$ obie strony powyższej równości są równe $0$ . Załóżmy więc, że zależność (1) jest prawdziwa dla pewnego $n$ . Wówczas

$ \begin{split} x_{0}+x_{1}+x_{2}+\ldots+x_{n}+x_{n+1}=\frac{1}{2}(x_{n}^{2}+2x_{n}-n)+x_{n+1}=\\ \qquad =\frac{1}{2}((x_{n}+1)^{2}-(n+1))+x_{n+1}=\frac{1}{2}(x_{n+1}^{2}-(n+1))+x_{n+1}=\\ \qquad =\frac{1}{2}(x_{n+1}^{2}+2x_{n+1}-(n+1)), \end{split} $

co kończy dowód indukcyjny wzoru (1).

Zatem

$ |x_{1}+x_{2}+\ldots+x_{2000}|=\frac{1}{2}|x_{2000}^{2}+2x_{2000}-2000|=\frac{1}{2}|(x_{2000}+1)^{2}-2001|. $

Liczbą kwadratową leżącą najbliżej liczby $2001$ jest $2025 = 45^2$ . Stąd oraz z powyższej równości wnioskujemy, że wyrażenie $|x_1 + x_2 +\ldots + x_{2000}|$ nie może przyjąć wartości mniejszej niż $\frac{1}{2}|2025 - 2001| =12$ .

Pozostaje zauważyć, że wartość $12$ można zrealizować przyjmując

$ x_n=\left\{\begin{array}{rl} n&\textrm{dla}\ n \leq 44;\\ -45&\textrm{dla}\ n > 44, n\ \textrm{nieparzyste};\\ 44&\textrm{dla}\ n > 44, n\ \textrm{parzyste}. \end{array}\right. $

Powyższy ciąg spełnia warunki zadania. Ponadto $x_{2000} = 44$ , co na mocy równości (1) daje $|x_1 + x_2 +\ldots + x_{2000}| = 12$ .

LII OM - II etap

II etap LII Olimpiady Matematycznej

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

LII OM - II - Zadanie 1

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Dane są liczby naturalne $k$ , $n$ większe od $1$ , przy czym liczba $p = 2k-1$ jest pierwsza. Dowieść, że jeżeli liczba

$ {n \choose 2} - {k \choose 2} $

jest podzielna przez $p$ , to jest ona podzielna przez $p^2$ .

Rozwiązanie

Liczba $p$ jest dzielnikiem liczby

$ a=\frac{n(n-1)}{2}-\frac{k(k-1)}{2}=\frac{(4n^{2}-4n+1)-(4k^{2}-4k+1)}{8}=\frac{(2n-1)^{2}-p^{2}}{8}. $

Zatem $p$ , jako liczba nieparzysta, jest dzielnikiem liczby $(2n - 1)^2 - p^2$ . Liczba $p$ jest pierwsza, skąd $p | (2n-1)$ . Z podzielności tej wynika, że $p^2 | (2n - 1)^2$ , czyli $p^2 | a$ .

LII OM - II - Zadanie 2

Zawody matematyczne:

LIII OM, 2001-2002

Etap:

Punkty $A$ , $B$ , $C$ leżą w tej właśnie kolejności na jednej prostej, przy czym $AB < BC$ . Punkty $D$ , $E$ są wierzchołkami kwadratu $ABDE$ . Okrąg o średnicy $AC$ przecina prostą $DE$ w punktach $P$ i $Q$ , przy czym punkt $P$ należy do odcinka $DE$ . Proste $AQ$ i $BD$ przecinają się w punkcie $R$ . Udowodnić, że $DP = DR$ .

Rozwiązanie

Kąt $APC$ jest prosty jako kąt wpisany oparty na średnicy (rys. 1). Stąd

$ \measuredangle EAP = 90^\circ - \measuredangle PAC = \measuredangle ACP. $

Z kolei z równości łuków $AP$ i $CQ$ wynika równość kątów $ACP$ i $CAQ$ , skąd

$ \measuredangle EAP = \measuredangle BAR. $

Trójkąty $PAE$ i $RBA$ są więc przystające (cecha kąt-bok-kąt), co dowodzi, że $EP = BR$ . Stąd $DP = DR$ .

LII OM - II - Zadanie 3

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Niech $n \geq 3$ będzie liczbą naturalną. Dowieść, że dowolny wielomian postaci

$ x^{n}+a_{n-3}x^{n-3}+a_{n-4}x^{n-4}+a_{n-5}x^{n-5}+\ldots+a_{1}x+a_{0}, $

gdzie co najmniej jeden ze współczynników rzeczywistych $a_0,a_1,\ldots, a_{n-3}$ jest różny od zera, ma mniej niż $n$ pierwiastków rzeczywistych (każdy pierwiastek liczymy tyle razy, ile wynosi jego krotność).

Rozwiązanie

Przypuśćmy, że dany w treści zadania wielomian ma $n$ pierwiastków rzeczywistych $x_1,x_2,\ldots,x_n$ . Ze wzorów Viete'a wynika, że

$ x_{1}+x_{2}+\ldots+x_{n}=-a_{n-1}=0\ \textrm{oraz}\sum_{1\leq i<j\leq n}x_{i}x_{j}=a_{n-2}=0. $

Zatem $x_1^2 + x_2^2 +\ldots + x_n^2 =a_{n-1}^2 - 2a_{n-2} = 0$ , skąd $x_1 = x_2 = \ldots = x_n = 0$ . Jednak powyższa równość pociąga za sobą $a_0 = a_1 = \ldots = a_{n-3} =0$ , co przeczy założeniu.

Otrzymana sprzeczność dowodzi, że dany wielomian stopnia n nie może mieć $n$ pierwiastków rzeczywistych, zatem musi ich mieć mniej niż $n$ .

LII OM - II - Zadanie 4

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Wyznaczyć wszystkie liczby naturalne $n \geq 3$ , dla których prawdziwe jest następujące zdanie:

W dowolnym $n$ -wyrazowym ciągu arytmetycznym $a_1, a_2,\ldots,a_n$ , dla którego liczba $1 \cdot a_1 + 2\cdot a_2 +... + n \cdot a_n$ jest wymierna, istnieje wyraz będący liczbą wymierną.

Rozwiązanie

Odpowiedź: Rozpatrywane zdanie jest prawdziwe jedynie dla liczb $n \geq 3$ dających z dzielenia przez $3$ resztę $1$ .

Niech $a_i = a + ir$ ( $i = 1,2,\ldots,n$ ) będzie ciągiem arytmetycznym. Korzystając ze wzorów

$ 1+2+\ldots+n = \frac{n(n+1)}{2} \ \text{oraz}\ 1^{2}+2^{2}+\ldots+n^{2} = \frac{n(n+1)(2n+1)}{6} $

stwierdzamy, że dana w treści zadania suma jest równa

$ S=\frac{n(n+1)}{2}a+\frac{n(n+1)(2n+1)}{6}r. $

Stąd uzyskujemy

$ (1)\qquad \frac{2S}{n(n+1)}=a+\frac{2n+1}{3}r. $

Załóżmy najpierw, że liczba $n$ daje z dzielenia przez $3$ resztę $1$ . Wówczas liczba $k = \frac{1}{3}(2n +1)$ jest całkowita. Z równości (1) oraz z faktu, że $S$ jest liczbą wymierną wynika, że wyraz $a_k$ jest liczbą wymierną. Zatem rozpatrywane zdanie jest w tym przypadku prawdziwe.

Załóżmy z kolei, że liczba $n$ nie daje z dzielenia przez $3$ reszty $1$ (innymi słowy, liczba $\frac{1}{3} (2n + 1)$ nie jest całkowita). Skonstruujemy ciąg arytmetyczny $a_i$ , dla którego rozpatrywane zdanie nie jest prawdziwe. Przyjmijmy:

$ r = \sqrt{2}\ \textrm{oraz}\ a = -\frac{1}{3} (2n + 1)\sqrt{2}. $

Ze związku (1) otrzymujemy $S = 0$ , jednak dla dowolnego $i \in \{1,2,...,n\}$ liczba

$ a_{i}=\left(i-\frac{1}{3}(2n+1)\right)\sqrt{2} $

jest niewymierna. Rozpatrywane zdanie nie jest więc prawdziwe, jeśli $n$ nie daje z dzielenia przez $3$ reszty $1$ .

LII OM - II - Zadanie 5

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Punkt $I$ jest środkiem okręgu wpisanego w trójkąt $ABC$ . Prosta $AI$ przecina bok $BC$ w punkcie $D$ . Dowieść, że $AI + CD = AC$ wtedy i tylko wtedy, gdy $\measuredangle B = 60^\circ + \frac{1}{3}\measuredangle C$ .

Rozwiązanie

Niech $E$ będzie takim punktem leżącym na boku $AC$ , że $AI = AE$ (rys. 1). Wówczas

$ \begin{split} AI + CD = AC & \Leftrightarrow CE = CD\\ &\Leftrightarrow \textrm{trójkąty}\ CDI\ \textrm{i}\ CEI\ \textrm{są przystające}\\ &\Leftrightarrow \measuredangle AEI = \measuredangle ADB\\ &\Leftrightarrow \textrm{trójkąty}\ AIE\ \textrm{i}\ ABD\ \textrm{są podobne}\\ &\Leftrightarrow \measuredangle B = \measuredangle ADB\\ &\Leftrightarrow \measuredangle B = \frac{1}{2}\measuredangle A + \measuredangle C\\ &\Leftrightarrow \measuredangle B = 60^\circ +\frac{1}{3} \measuredangle C. \end{split} $

LII OM - II - Zadanie 6

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Dla danej liczby całkowitej dodatniej $n$ rozstrzygnąć, czy podzbiorów $n$ -elementowych zbioru $\{1,2,3,\ldots,2n-1,2n\}$ mających sumę elementów parzystą jest tyle samo, co podzbiorów $n$ -elementowych mających nieparzystą sumę elementów. Jeśli nie, to rozstrzygnąć, których jest więcej i o ile.

Rozwiązanie

Połączmy liczby ze zbioru $S = \{1,2,3,\ldots,2n-1,2n\}$ w pary:

$ (1,2),\ (3,4),\ \ldots, (2n-1,2n). $

Niech $X$ będzie dowolnym $n$ -elementowym podzbiorem zbioru $S$ . Wybierzmy (jeśli jest to możliwe) najmniejszą liczbę $x$ ze zbioru $X$ o tej własności, że liczba $y$ występująca w parze z liczbą $x$ nie należy do zbioru $X$ . Następnie usuńmy ze zbioru $X$ element $x$ zastępując go elementem $y$ . Otrzymany zbiór nazwijmy $f(X)$ . Zbiory $X$ i $f(X)$ mają sumy elementów różnej parzystości.

W dalszej części rozwiązania rozpatrzymy dwa przypadki:

(a) Liczba $n$ jest nieparzysta.

Odwzorowanie $f$ jest określone dla dowolnego $n$ -elementowego podzbioru zbioru $S$ i łączy ono w pary $(X,f(X))$ wszystkie podzbiory $n$ -elementowe o nieparzystej sumie elementów ze wszystkimi $n$ -elementowymi podzbiorami o sumie elementów parzystej. To dowodzi, że $n$ -elementowych podzbiorów o parzystej sumie elementów jest tyle samo, co $n$ -elementowych podzbiorów o nieparzystej sumie elementów.

(b) Liczba $n$ jest parzysta.

W tym przypadku odwzorowania $f$ nie da się określić jedynie na tych $n$ -elementowych podzbiorach zbioru $S$ , które są złożone z pełnych par. Zbiorów tych jest $n \choose {n/2}$ i wszystkie one mają sumę elementów o takiej samej parzystości, jak parzystość liczby $n/2$ . Pozostałe podzbiory możemy połączyć w pary $(X,f(X))$ . Jeżeli $n$ dzieli się przez cztery, to $n$ -elementowych podzbiorów o parzystej sumie elementów jest o ${n \choose n/2}$ więcej niż $n$ -elementowych podzbiorów o nieparzystej sumie elementów. Jeśli natomiast $n$ nie dzieli się przez cztery, to podzbiorów o nieparzystej sumie elementów jest o ${n \choose n/2}$ więcej.

LII OM - III etap

III etap LII Olimpiady Matematycznej

Załącznik	Wielkość
LII OM III etap - Zadania [4]	78.81 KB
LII OM III etap - Zadania z rozwiązaniami [5]	175.32 KB

LII OM - III - Zadanie 1

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dowieść, że dla każdej liczby naturalnej $n \geq 2$ i dowolnych liczb rzeczywistych nieujemnych $x_1,x_2,\ldots,x_n$ zachodzi nierówność

$ \sum_{i=1}^{n}ix_{i}\leq{n \choose 2}+\sum_{i=1}^{n}x_{i}^{i}. $

Rozwiązanie

Z nierówności między średnią geometryczną i średnią arytmetyczną zastosowanej do liczb

$ y_{1}=x_{i}^{i},\ y_{2}=y_{3}=\ldots=y_{i}=1\ (2\leq i\leq n) $

otrzymujemy

$ x_{i}=\sqrt[i]{y_{1}y_{2}y_{3}\ldots y_{i}}\leq\frac{y_{1}+y_{2}+y_{3}+\ldots+y_{i}}{i}=\frac{x_{i}^{i}+(i-1)}{i}. $

Zatem

$ \sum_{i=1}^{n}ix_{i}\leq\sum_{i=1}^{n}(i-1)+\sum_{i=1}^{n}x_{i}^{i},\ \textrm{czyli}\ \sum_{i=1}^{n}ix_{i}\leq{n \choose 2}+\sum_{i=1}^{n}x_{i}^{i}. $

LII OM - III - Zadanie 2

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dowieść, że suma odległości dowolnego punktu leżącego wewnątrz czworościanu foremnego o krawędzi $1$ od jego wierzchołków jest nie większa niż $3$ .

Rozwiązanie

Niech $A_1 A_2 A_3 A_4$ będzie danym czworościanem, a $P$ dowolnym punktem w jego wnętrzu. Załóżmy, że prosta $A_i P$ przecina przeciwległą ścianę czworościanu $A_1 A_2 A_3 A_4$ w punkcie $B_i$ . Niech $\mathcal{C}_i$ będzie czworościanem, którego jedną ścianą jest ta ściana czworościanu $A_1 A_2A_3A_4$ , która zawiera punkt $B_i$ , zaś przeciwległym wierzchołkiem punkt $P$ . Wtedy

$ \sum_{i=1}^{4}\frac{PB_{i}}{A_{i}B_{i}}=\sum_{i=1}^{4}\frac{V(\mathcal{C}_{i})}{V(A_{1}A_{2}A_{3}A_{4})}=1, \quad \textrm{stąd} \quad \sum_{i=1}^{4}\frac{A_{i}P}{A_{i}B_{i}}=3. $

( $V(\mathcal{T})$ oznacza objętość czworościanu $\mathcal{T}$ .) Z nierówności $A_iB_i < 1$ oraz z powyższej zależności wynika teza.

LII OM - III - Zadanie 3

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Rozważamy ciąg $(x_n)$ określony rekurencyjnie wzorami

$ x_{1}=a,\ x_{2}=b\ \textrm{oraz}\ x_{n+2}=x_{n+1}+x_{n}\ \textrm{dla}\ n=1,2,3,\ldots, $

gdzie $a$ i $b$ są liczbami rzeczywistymi.

Liczbę $c$ będziemy nazywać wartością wielokrotną ciągu $(x_n)$ , jeżeli istnieją co najmniej dwie różne liczby całkowite dodatnie $k$ i $l$ takie, że $x_k = x_l = c$ . Wykazać, że można tak dobrać liczby $a$ i $b$ , aby ciąg $(x_n)$ miał więcej niż $2000$ wartości wielokrotnych, ale nie można tak dobrać $a$ i $b$ , aby miał on nieskończenie wiele wartości wielokrotnych.

Rozwiązanie

Ciąg $(x_n)$ spełnia taką samą rekurencję, jak ciąg Fibonacciego

$ F_{1}=F_{2}=1,\ F_{n+2}=F_{n+1}+F_{n}\ \textrm{dla}\ n=1,2,3,\ldots. $

Niech dodatkowo $F_0 = 0$ oraz $F_{-n} = (-1)^{n+1}F_n$ dla $n = 1,2,3,\ldots$ . Wówczas równość $F_{n+2} = F_{n+1} + F_n$ zachodzi dla dowolnej liczby całkowitej $n$ .

Przyjmijmy $a = F_{-4001}$ oraz $b = F_{-4000}$ . Wtedy $x_n = F_{n-4002}$ . Ponadto dla $n = 1,3,5,7,\ldots,4001$ uzyskujemy $x_n = F_{n-4002} = F_{4002-n} = x_{8004-n}$ . Stąd wynika, że liczby $F_1,F_3,F_5,\ldots,F_{4001}$ są wartościami wielokrotnymi ciągu $(x_n)$ ; są one różne i jest ich więcej niż $2000$ .

Dla dowolnego ciągu $(x_n)$ spełniającego warunek

$ x_{n+2} = x_{n+1} + x_n \ \textrm{dla}\ n = 1,2,3,\ldots $

istnieją takie liczby rzeczywiste $A$ i $B$ , że

$ x_{n}=A\alpha^{n}+B\beta^{n}\text{ }dla\text{ }n=1,2,3,\ldots, $

gdzie $\alpha=\frac{1}{2}(1+\sqrt{5})$ , $\beta=\frac{1}{2}(1-\sqrt{5})$ są pierwiastkami wielomianu $x^2-x - 1$ .

Jeżeli $A = B = 0$ , to wszystkie wyrazy ciągu $(x_n)$ są zerami i liczba $0$ jest jedyną wartością wielokrotną ciągu $(x_n)$ .

Jeżeli $A = 0$ oraz $B \neq 0$ , to wszystkie wyrazy ciągu $(x_n)$ są różne i ciąg $(x_n)$ nie ma wartości wielokrotnych.

Jeżeli natomiast $A \ne 0$ , to

$ \lim_{n\to \infty} x_n=\left\{\begin{array}{ll} +\infty&\textrm{gdy}\ A>0,\\ -\infty&\textrm{gdy}\ A<0. \end{array}\right. $

Zatem istnieje taka liczba naturalna $N$ , że dla wszystkich $n \geq N$ , $x_n \ne 0$ . Ponadto

$ \frac{x_{n+1}}{x_{n}}=\frac{A\alpha^{n+1}+B\beta^{n+1}}{A\alpha^{n}+B\beta^{n}}=\frac{A\alpha+B\beta(\frac{\beta}{\alpha})^{n}}{A+B(\frac{\beta}{\alpha})^{n}}\ (n\geq N), $

a zatem $\lim_{n\to \infty} \frac{x_{n+1}}{x_n} =\alpha>1$ .

Stąd wynika, że ciąg $(x_n)$ od pewnego miejsca jest rosnący i w związku z tym nie może mieć nieskończenie wielu wartości wielokrotnych.

LII OM - III - Zadanie 4

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dane są takie liczby całkowite $a$ i $b$ , że dla każdej liczby całkowitej nieujemnej $n$ liczba $2^na + b$ jest kwadratem liczby całkowitej. Dowieść, że $a = 0$ .

Rozwiązanie

Jeżeli $b = 0$ , to $a = 0$ , gdyż dla $a \ne 0$ liczby $a$ i $2a$ nie mogą być jednocześnie kwadratami liczb całkowitych.

Gdyby liczba $a$ była ujemna, to dla pewnej, dużej liczby naturalnej $n$ , liczba $2^n a + b$ też byłaby ujemna, nie mogłaby więc być kwadratem liczby całkowitej.

Pozostaje do rozpatrzenia przypadek, gdy $a \geq 0$ oraz $b \neq 0$ .

Dla każdej liczby całkowitej dodatniej $k$ , liczby

$ 2^{2k} a + b \ \textrm{oraz}\ 4(2^{2k-2} a + b) = 2^{2k} a + 4b $

są kwadratami różnych liczb całkowitych nieujemnych, powiedzmy

$ 2^{2k}a+b=x_{k}^{2}\ \textrm{oraz}\ 2^{2k}a+4b=y_{k}^{2}. $

Wówczas $x_{k}+y_{k}\leq(x_{k}+y_{k})|x_{k}-y_{k}|=|x_{k}^{2}-y_{k}^{2}|=|3b|$ , skąd

$ 2^{2k}a+b=x_{k}^{2}\leq(x_{k}+y_{k})^{2}\leq 9b^{2}\ \textrm{dla każdego $k$.} $

Zatem ciąg $(x_k)$ jest ograniczony, co jest możliwe tylko wtedy, gdy $a = 0$ .

LII OM - III - Zadanie 5

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Punkty $K$ i $L$ leżą odpowiednio na bokach $BC$ i $CD$ równoległoboku $ABCD$ , przy czym $BK \cdot AD = DL \cdot AB$ . Odcinki $DK$ i $BL$ przecinają się w punkcie P. Wykazać, że $\measuredangle DAP = \measuredangle BAC$ .

Rozwiązanie

Niech $Y$ będzie punktem przecięcia prostych $AP$ i $CD$ oraz niech $X$ będzie punktem przecięcia prostych $DK$ i $AB$ (rys. $1$ i $2$ ). Wówczas

$ \frac{DL}{DY}=\frac{BX}{AX}=\frac{BK}{AD}. $

Stąd oraz z równości danej w treści zadania otrzymujemy:

$ \frac{DY}{AD}=\frac{DL}{BK}=\frac{AD}{AB}=\frac{BC}{AB}. $

To dowodzi, że trójkąty $ABC$ i $ADY$ są podobne, skąd wynika teza.

LII OM - III - Zadanie 6

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dane są liczby całkowite dodatnie $n_1 <n_2 < \ldots <n_{2000} < 10^{100}$ . Dowieść, że ze zbioru $\{n_1,n_2,\ldots,n_{2000}\}$ można wybrać niepuste rozłączne podzbiory $A$ i $B$ mające tyle samo elementów, taką samą sumę elementów i taką samą sumę kwadratów elementów.

Rozwiązanie

Dla zbioru $X \subseteq \{n_1,n_2,\ldots,n_{2000}\}$ niech $s_0(X)$ , $s_1(X)$ i $s_2(X)$ oznaczają odpowiednio liczbę elementów, sumę elementów i sumę kwadratów elementów zbioru $X$ .

Wystarczy udowodnić, że istnieją takie dwa różne podzbiory $C$ i $D$ zbioru $\{n_1,n_2,\ldots,n_{2000}\}$ , dla których $s_i(C) = s_i(D)$ dla $i = 0,1,2$ . Wówczas zbiory $A = C \setminus D$ oraz $B = D\setminus C$ są niepuste i spełniają warunki zadania.

Dla dowolnego podzbioru $X$ zbioru $\{n_1 , n_2, \ldots ,n_{2000}\}$ mamy

$ (1) \qquad s_0(X) < 10^4,\ s_1(X) < 2000 \cdot 10^{100} < 10^{104}, s_2(X) < 2000\cdot 10^{200} < 10^{204}. $

Oznaczając $S(X) = s_0(X) + 10^4s_1(X) + 10^{108}s_2(X)$ uzyskujemy

$ S(X) < 10^{313} < (10^3)^{105} < 2^{1050} < 2^{2000} . $

Stąd istnieją takie dwa różne podzbiory $C$ , $D$ zbioru $\{n_1 , n_2, \ldots ,n_{2000}\}$ , że $S(C) = S(D)$ . Z nierówności (1) wynika, że $s_i(C) = s_i(D)$ dla $i = 0, 1, 2$ , co kończy rozwiązanie zadania.