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