XVIII ZMPB

Zadania z XVIII Zawodów Matematycznych Państw Bałtyckich

Załącznik	Wielkość
XVIII ZMPB - Zadania z rozwiązaniami [1]	198.14 KB

XVIII ZMPB - Zadanie 1

Zawody matematyczne:

XVIII ZMPB, 2007

Dla dodatniej liczby całkowitej $n$ rozważmy rozbicie zbioru $\{1,2,\ldots,2n\}$ na $n$ podzbiorów dwuelementowych $P_1$ , $P_2$ , $\ldots$ , $P_n$ . W każdym zbiorze $P_i$ niech $p_i$ będzie iloczynem obu elementów zbioru $P_i$ . Udowodnić, że

$ {1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}<1. $

Rozwiązanie

Istnieje tylko skończenie wiele sposobów rozbicia zbioru $\{1,2,\ldots,2n\}$ na $n$ podzbiorów dwuelementowych, więc wśród wszystkich wartości wyrażenia ${1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}$ odpowiadających tym rozbiciom istnieje wartość największa. Udowodnimy, że ta największa wartość odpowiada rozbiciu

$ \{1,2,\ldots,2n\}=\{1,2\}\cup\{3,4\}\cup\ldots\cup\{2n-1,2n\}. (1) \qquad $

Rozpatrzmy w tym celu dowolne inne rozbicie

$ \{1,2,\ldots,2n\}=P_1\cup P_2\cup\ldots\cup P_n, $

Ponieważ jest to rozbicie różne od (1), więc istnieje taka najmniejsza liczba $k\in\{1,2,\ldots,n\}$ , że liczby $2k-1$ i $2k$ nie należą do tego samego zbioru danego rozbicia. Możemy przyjąć, że

$ P_1=\{2k-1,a\},\qquad P_2=\{2k,b\}, $

gdzie liczby $a$ i $b$ są różne i większe od $2k$ . Przyjmijmy

$ P_1'=\{2k-1,2k\},\qquad P_2'=\{a,b\}. $

Wówczas rozbiciom

$ (2) \qquad P_1\cup P_2\cup P_3\cup\ldots\cup P_n\quad\hbox{oraz}\quad P_1'\cup P_2'\cup P_3\cup\ldots\cup P_n $

odpowiadają następujące wartości danego w treści zadania wyrażenia:

$ {1\over (2k-1)a}+{1\over 2k\cdot b}+{1\over p_3}+\ldots+{1\over p_n} \quad\hbox{oraz}\quad {1\over (2k-1)\cdot 2k}+{1\over ab}+{1\over p_3}+\ldots+{1\over p_n}. $

Obliczamy, że różnica dwóch powyższych liczb wynosi

$ {1\over (2k-1)\cdot 2k}+{1\over ab}-{1\over (2k-1)a}-{1\over 2k\cdot b}= {(a-2k)(b-(2k-1))\over(2k-1)2kab}>0. $

Zatem drugiemu z rozbić (2) odpowiada większa wartość wyrażenia. Wynika stąd, że żadnemu rozbiciu różnemu od rozbicia (1) nie może odpowiadać największa wartość wyrażenia ${1\over p_1}+{1 \over p_2}+\ldots+{1\over p_n}$ .

Dowiedliśmy w ten sposób nierówności

$ {1\over p_1}+{1\over p_2}+\ldots+{1\over p_n}\le {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n}. $

Aby dokończyć rozwiązanie, wystarczy sprawdzić, że

$ {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n}<1. $

Zauważmy w tym celu, że

$ {1\over m(m+1)}={1\over m}-{1\over m+1} $

dla dowolnej liczby całkowitej $m\ge 1$ , skąd dostajemy

$ \begin{split} {1\over 1\cdot 2}+{1\over 3\cdot 4}+\ldots+{1\over (2n-1)\cdot 2n} &\le7{1\over 1\cdot 2}+{1\over 2\cdot 3}+\ldots+{1\over n(n+1)}= \\ &= 1-{1\over 2}+{1\over 2}-{1\over 3}+\ldots+{1\over n}-{1\over n+1}= \\ &= 1-{1\over n+1}<1. \end{split} $

XVIII ZMPB - Zadanie 2

Zawody matematyczne:

XVIII ZMPB, 2007

Ciąg liczb całkowitych $a_1$ , $a_2$ , $a_3$ , $\ldots$ nazwiemy dokładnym, jeżeli

$ a_n^2-a_m^2=a_{n-m}a_{n+m} \qquad\hbox{dla }n\ge m. $

Wykazać, że istnieje ciąg dokładny, w którym $a_1=1$ , $a_2=0$ , i wyznaczyć $a_{2007}$ .

Rozwiązanie

Wykażemy, że jedynym ciągiem dokładnym $a_1$ , $a_2$ , $a_3$ , $\ldots$ , w którym $a_1=1$ oraz $a_2=0$ , jest ciąg określony wzorem

$ (1) \qquad a_n= \begin{cases} 0, & \text{ gdy } $2\,|\,n$,\\ 1, & \text{ gdy } $n\equiv 1\,\,\mod{4}$,\\ -1,& \text{ gdy } $n\equiv 3\,\,\mod{4}$.\\ \end{cases} $

Przypuśćmy więc, że $a_1$ , $a_2$ , $a_3$ , $\ldots$ jest ciągiem dokładnym i $a_1=1$ , $a_2=0$ . Udowodnimy indukcyjnie wzór (1). Dla $n=1$ i $n=2$ jest on prawdziwy. Załóżmy z kolei, iż zależność (1) jest spełniona dla $n=2k-1$ i $n=2k$ . Wynika stąd w szczególności, że $a_{2k}=0$ . Korzystając z dokładności danego ciągu obliczamy

$ a_{2k-1}a_{2k+1}=a_{2k}^2-a_1^2=0-1=-1, $

skąd otrzymujemy równość $a_{2k+1}=-a_{2k-1}$ . Ponadto

$ a_{2k+2}^2-a_{2k}^2=a_2a_{4k+2}=0, $

gdyż $a_2=0$ . Wobec tego $a_{2k+2}^2=a_{2k}^2=0$ , czyli $a_{2k+2}=0$ . To kończy dowód indukcyjny równości (1).

Pozostaje sprawdzić, że ciąg określony warunkiem (1) jest ciągiem dokładnym. W tym celu niech $n>m$ będą dodatnimi liczbami całkowitymi. Rozważmy trzy przypadki:

Obie liczby $n$ i $m$ są nieparzyste lub obie są parzyste.

Jeżeli liczby $n$ i $m$ są nieparzyste, to każda z liczb $a_n$ , $a_m$ jest równa $1$ albo $-1$ ; jeśli zaś liczby $n$ i $m$ są parzyste, to $a_n=a_m=0$ . Zatem $a_n^2-a_m^2=0$ . Z drugiej strony, liczby $n-m$ i $n+m$ są parzyste, więc $a_{n-m}=a_{n+m}=0$ .
Liczba $n$ jest parzysta, zaś liczba $m$ jest nieparzysta.
W tym przypadku mamy $a_n=0$ i $a_m=\pm 1$ , czyli $a_n^2-a_m^2=-1$ . Ponadto liczby nieparzyste $n-m$ i $n+m$ dają te same reszty z dzielenia przez $4$ , gdyż ich suma $2n$ jest podzielna przez $4$ . Otrzymujemy stąd $a_{n-m}=a_{n+m}=\pm 1$ , co daje $a_{n-m}a_{n+m}=1$ .
Liczba $n$ jest nieparzysta, zaś liczba $m$ jest parzysta.

Wówczas $a_n=\pm 1$ , $a_m=0$ oraz $a_n^2-a_m^2=1$ . Z kolei liczby nieparzyste $n-m$ i $n+m$ dają różne reszty z dzielenia przez $4$ , ich suma $2n$ nie jest bowiem podzielna przez $4$ . W efekcie jedna z liczb $a_{n-m}$ , $a_{n+m}$ jest równa $1$ , a druga jest równa $-1$ . To oznacza, że $a_{n-m}a_{n+m}=-1$ .

Widzimy, że we wszystkich przypadkach równość $a_n^2-a_m^2=a_{n-m}a_{n+m}$ jest prawdziwy.

Ponieważ $2007\equiv 3\,\mod{4}$ , więc szukana wartość wynosi $a_{2007}=-1$ .

XVIII ZMPB - Zadanie 3

Zawody matematyczne:

XVIII ZMPB, 2007

Niech $F$ , $G$ , $H$ będą takimi wielomianami stopnia co najwyżej $2n+1$ o współczynnikach rzeczywistych, że:

Dla wszystkich liczb rzeczywistych $x$ mamy

$ F(x)\le G(x)\le H(x). $
Istnieją takie różne liczby rzeczywiste $x_1$ , $x_2$ , $\ldots$ , $x_n$ , że

$ F(x_i)=H(x_i)\qquad\hbox{dla }i=1,2,\ldots,n. $
Istnieje liczba rzeczywista $x_0$ różna od $x_1$ , $x_2$ , $\ldots$ , $x_n$ , dla której

$ F(x_0)+H(x_0)=2G(x_0). $

Dowieść, że

$ F(x)+H(x)=2G(x) $

dla wszystkich liczb rzeczywistych $x$ .

Rozwiązanie

Rozpatrzmy wielomiany $P$ i $Q$ określone wzorami

$ P(x)=G(x)-F(x), \qquad Q(x)=H(x)-F(x). $

Są to wielomiany stopnia co najwyżej $2n+1$ . Na mocy warunku (1) mamy

$ Q(x)\ge P(x)\ge 0 $

dla każdej liczby rzeczywistej $x$ . Z kolei warunek (2) implikuje, że

$ Q(x_i)=P(x_i)=0 \qquad\hbox{dla }i=1,2,\ldots,n. $

Ponieważ wielomiany $P$ i $Q$ przybierają tylko wartości nieujemne, więc liczby $x_1$ , $x_2$ , $\ldots$ , $x_n$ są pierwiastkami tych wielomianów o krotności co najmniej $2$ . Wobec tego wielomiany te są podzielne przez wielomian

$ R(x)=(x-x_1)^2(x-x_2)^2\ldots(x-x_n)^2. $

Ponadto ilorazy $P(x)/ R(x)$ i $Q(x)/ R(x)$ są wielomianami przyjmującymi tylko wartości nieujemne. Z drugiej strony, stopnie wielomianów $P$ i $Q$ nie przekraczają $2n+1$ , zaś $R$ jest wielomianem stopnia $2n$ . Wynika stąd, że ilorazy $P(x)/ R(x)$ i $Q(x)/ R(x)$ są wielomianami stopnia co najwyżej $1$ przyjmującymi tylko wartości nieujemne. Są to więc wielomiany stałe.

Udowodniliśmy zatem istnienie takich liczb rzeczywistych $a$ i $b$ , że

$ P(x)=aR(x), \qquad Q(x)=bR(x) $

dla wszystkich liczb rzeczywistych $x$ . Korzystając z warunku (3) dostajemy

$ bR(x_0)=Q(x_0)=H(x_0)-F(x_0)=2G(x_0)-2F(x_0)=2P(x_0)=2aR(x_0). $

Liczba $x_0$ jest różna od każdej z liczb $x_1$ , $x_2$ , $\ldots$ , $x_n$ , nie jest więc pierwiastkiem wielomianu $R$ . Wobec tego z powyższej równości wynika, że $b=2a$ i w konsekwencji dla dowolnej liczby rzeczywistej $x$ otrzymujemy

$ F(x)+H(x)-2G(x)=Q(x)-2P(x)=(b-2a)R(x)=0, $

co kończy rozwiązanie zadania.

XVIII ZMPB - Zadanie 4

Zawody matematyczne:

XVIII ZMPB, 2007

Niech $a_1$ , $a_2$ , $\ldots$ , $a_n$ będą dodatnimi liczbami rzeczywistymi, i niech $S=a_1+a_2+\ldots+a_n$ . Udowodnić, że

$ \begin{split} (2S+n)(2S&+a_1a_2+a_2a_3+\ldots+a_na_1)\ge \\ &\ge 9\Bigl(\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1}\Bigr)^2. \end{split} $

Rozwiązanie

Zauważmy przede wszystkim, że

$ \begin{split} 2S-2(\sqrt{a_1a_2}&+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1})= \\ &=(\sqrt{a_1}-\sqrt{a_2})^2+(\sqrt{a_2}-\sqrt{a_3})^2+\ldots+ (\sqrt{a_n}-\sqrt{a_1})^2\ge 0, \end{split} $

skąd uzyskujemy nierówność

$ (1) \qquad 2S\ge 2(\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1}). $

Podnosząc tę nierówność stronami do kwadratu uzyskujemy

$ (2) \qquad 4S^2\ge 4\Bigl(\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1}\Bigr)^2. $

Korzystając z kolei z nierówności $x+y\ge 2\sqrt{xy}$ otrzymujemy

$ 1+a_1a_2\ge 2\sqrt{a_1a_2}, \quad 1+a_2a_3\ge 2\sqrt{a_2a_3}, \quad\ldots,\quad 1+a_na_1\ge 2\sqrt{a_na_1}, $

co prowadzi do związku

$ n+a_1a_2+a_2a_3+\ldots+a_na_1\ge 2(\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1}), $

który w połączeniu z zależnością (1) pozwala napisać

$ (3) \qquad 2S(n+a_1a_2+a_2a_3+\ldots+a_na_1)\ge 4\Bigl(\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1}\Bigr)^2. $

Wreszcie na mocy nierówności pomiędzy średnią arytmetyczną i kwadratową dostajemy

$ {a_1a_2+a_2a_3+\ldots+a_na_1\over n}\ge \Bigl({\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1}\over n}\Bigr)^2, $

i wobec tego

$ (4) \qquad n(a_1a_2+a_2a_3+\ldots+a_na_1)\ge \Bigl(\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots+\sqrt{a_na_1}\Bigr)^2. $

Dodając stronami nierówności (2), (3), (4) uzyskujemy tezę.

XVIII ZMPB - Zadanie 5

Zawody matematyczne:

XVIII ZMPB, 2007

Funkcja $f$ , określona na zbiorze wszystkich liczb rzeczywistych różnych od $0$ , przyjmuje wszystkie wartości rzeczywiste różne od $1$ . Ponadto

$ f(xy)=f(x)f(-y)-f(x)+f(y) $

dla dowolnych $x,y\ne 0$ , oraz

$ f(f(x))={1\over f({1\over x})} $

dla każdego $x\not\in\{0,1\}$ . Wyznaczyć wszystkie takie funkcje $f$ .

Rozwiązanie

W pierwszym równaniu danym w treści zadania przyjmujemy $y=1$ . Otrzymujemy

$ f(x)=f(x)f(-1)-f(x)+f(1),\quad\hbox{czyli}\quad f(x)\cdot (2-f(-1))=f(1) $

dla każdej liczby rzeczywistej $x\ne 0$ . Z założenia funkcja $f$ nie jest stała, więc wynika stąd, że $f(1)=0$ oraz $f(-1)=2$ . Następnie podstawiamy w pierwszym równaniu $y=-1$ i obliczamy, że

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

Oznaczmy

$ g(x)=1-f(x) $

dla każdej liczby rzeczywistej $x\ne 0$ . Równość (1) przepisujemy teraz w postaci

$ g(-x)=1-f(-x)=1-(2-f(x))=-(1-f(x))=-g(x). $

To oznacza, że funkcja $g$ jest nieparzysta.

Przekształcamy teraz pierwsze równanie z treści zadania:

$ \begin{split} g(xy)&=1-f(xy)=1-f(x)f(-y)+f(x)-f(y)=\\ &=1-(1-g(x))(1-g(-y))+(1-g(x))-(1-g(y))=\\ &=1-1+g(x)+g(-y)-g(x)g(-y)+1-g(x)-1+g(y)=\\ &=g(x)g(y). \end{split} $

Podstawiając $y=1/x$ w powyższej zależności stwierdzamy, że

$ (2) \qquad g\Bigl({1\over x}\Bigr)={1\over g(x)}. $

dla każdej liczby rzeczywistej $x\ne 0$ . Wykorzystując teraz drugie równanie w treści zadania oraz zależność (2) obliczamy, że

$ 1-g(1-g(x))=1-g(f(x))=f(f(x))={1\over f(\xfrac{1}{x})}= {1\over 1-g(\xfrac{1}{x})}={1\over 1-{1\over g(x)}} $

i w efekcie

$ (3) \qquad g(f(x))=g(1-g(x))=1-{1\over 1-{1\over g(x)}}={1\over 1-g(x)}= {1\over f(x)}. $

Funkcja $f$ przyjmuje wszystkie wartości rzeczywiste z wyjątkiem $1$ , więc równość (3) oznacza, że

$ g(y)={1\over y}\quad\hbox{dla }y\ne 0,1,\qquad\hbox{czyli}\qquad f(x)=1-{1\over x}\quad\hbox{dla }x\ne 0,1. $

Przy tym wyznaczona wcześniej wartość $f(1)=0$ również wynika z powyższego wzoru.

Bezpośrednio sprawdzamy, że taka funkcja $f$ spełnia warunki zadania.

Odpowiedź: Jedyną funkcją o żądanych własnościach jest $f(x)=1-{1\over x}$ .

XVIII ZMPB - Zadanie 6

Zawody matematyczne:

XVIII ZMPB, 2007

Fredek pisze liczby $1$ , $2$ , $\ldots$ , $n$ w pewnej kolejności, po czym sporządza listę wszystkich takich par $(i,j)$ , że $1\le i<j\le n$ oraz $i$ -ta liczba jest większa od $j$ -tej liczby w jego permutacji. Następnie Fredek wielokrotnie wykonuje następującą operację, dopóki jest możliwa: wybiera parę $(i,j)$ z bieżącej listy, zamienia miejscami liczbę $i$ -tą z liczbą $j$ -tą w bieżącej permutacji, i usuwa parę $(i,j)$ z listy. Wykazać, że Fredek może wybierać pary w takiej kolejności, że po zakończeniu procesu liczby w permutacji będą uporządkowane rosnąco.

Rozwiązanie

Rozpocznijmy od następującego spostrzeżenia: jeżeli liczby w permutacji nie są uporządkowane rosnąco, to istnieją takie pozycje o numerach $i$ , $j$ , przy czym $i<j$ , że $i$ -ta liczba w permutacji jest większa o $1$ od liczby $j$ -tej. By udowodnić to spostrzeżenie, określmy $i$ jako pierwszą taką pozycję w permutacji, że stojąca na niej liczba $k$ jest różna od $i$ . Wówczas permutacja rozpoczyna się od liczb $1$ , $2$ , $\ldots$ , $i-1$ ; ponieważ $k>i$ , więc $k-1>i-1$ i wobec tego liczba $k-1$ występuje w rozważanej permutacji na pozycji o numerze $j>i$ . Wówczas numery $i$ , $j$ mają postulowaną własność.

Niech teraz dana będzie dowolna początkowa permutacja liczb $1$ , $2$ , $\ldots$ , $n$ i niech $(i,j)$ będzie parą numerów mających powyższą własność. Para ta oczywiście znajduje się na początkowej liście. Przypuśćmy, że Fredek wybiera tę właśnie parę i zamienia miejscami liczbę $i$ -tą z liczbą $j$ -tą. Ponieważ te dwie liczby są kolejnymi liczbami całkowitymi, więc liczba stojąca na dowolnej innej pozycji jest albo mniejsza od obu zamienianych liczb, albo też jest od nich większa. Stąd wniosek, że lista takich par $(i',j')$ , dla których $i'<j'$ oraz $i'$ -ta liczba w nowo otrzymanej permutacji jest większa od liczby $j'$ -tej, będzie tożsama z listą, którą Fredek otrzymuje usuwając z początkowej listy parę $(i,j)$ .

Następnie z każdą otrzymywaną permutacją Fredek wykonuje analogiczną operację - zamienia miejscami dwie kolejne liczby całkowite w permutacji, z których większa stoi na wcześniejszej pozycji. Wówczas na każdym kroku bieżąca lista par jest zgodna z wszystkimi relacjami mniejszości w bieżacej permutacji, czyli zgodna z listą wszystkich takich par $(i',j')$ , dla których $i'<j'$ oraz $i'$ -ta liczba w bieżącej permutacji jest większa od liczby $j'$ -tej.

Ponieważ początkowa lista Fredka zawierała skończenie wiele par, więc po wybraniu wszystkich par w opisanej kolejności pozostanie pusta lista par, która będzie zgodna z wszystkimi relacjami mniejszości w końcowej permutacji. Wobec tego w tej permutacji liczby będą uporządkowane rosnąco.

Uwaga: Zauważmy, że nie dla każdego wyboru pary $(i,j)$ stwierdzenie z ostatniego zdania drugiego akapitu rozwiązania jest prawdziwe. Na przykład dla $n=5$ i początkowej permutacji $5$ , $1$ , $3$ , $4$ , $2$ lista ma postać $(1,2)$ , $(1,3)$ , $(1,4)$ , $(1,5)$ , $(3,5)$ , $(4,5)$ . Wybierając parę $(1,3)$ i zamieniając w wyjściowej permutacji liczbę pierwszą z trzecią, Fredek uzyska permutację $3$ , $1$ , $5$ , $4$ , $2$ , w której trzecia liczba jest większa od czwartej, oraz listę nie zawierającą pary $(3,4)$ . Zatem lista po wykreśleniu jednej pary nie będzie zgodna z nową permutacją.

Istota rozumowania polega więc na możliwości wyboru takiej pary $(i,j)$ , dla której opisana operacja zachowuje zgodność listy z permutacją.

XVIII ZMPB - Zadanie 7

Zawody matematyczne:

XVIII ZMPB, 2007

Potworek składa się z sześciu trójkątów równobocznych o boku $1$ , jak pokazuje rysunek.

Wyznaczyć wszystkie liczby całkowite $n$ , dla których trójkąt równoboczny o boku $n$ można podzielić na potworki (obroty i odbicia potworków są dopuszczalne; potworki nie mogą na siebie zachodzić).

Rozwiązanie

Podzielmy trójkąt równoboczny o boku $n$ na $n^2$ trójkątów równobocznych o boku $1$ . Wówczas każdy potworek musi pokrywać dokładnie 6 takich trójkątów. Zatem warunkiem koniecznym istnienia podziału wyjściowego trójkąta na potworki jest podzielność $6\,|\,n^2$ , czyli podzielność $6\,|\,n$ .

Przyjmijmy teraz, że $n$ jest liczbą podzielną przez 6, ale niepodzielną przez 12; zatem $n=12k+6$ dla pewnej liczby całkowitej $k\ge 0$ . Pomalujmy każdy trójkąt równoboczny o boku 1 na biało albo czarno tak, by dwa trójkąty mające wspólny bok miały różne kolory oraz by trójkąty mające bok na brzegu wyjściowego trójkąta o boku $n$ były czarne (rys. 1).

Nietrudno spostrzec, że liczba czarnych trójkątów wynosi wówczas

$ 1+2+\ldots+n={n(n+1)\over 2}={(12k+6)(12k+7)\over 2}=(6k+3)(12k+7), $

jest zatem liczbą nieparzystą. Z drugiej strony, każdy potworek zawiera 2 albo 4 czarne trójkąty (rys. 2). To oznacza, że żądany podział nie jest możliwy.

Pozostaje do rozpatrzenia przypadek, gdy $12\,|\,n$ . Wykażemy, że wtedy istnieje postulowany podział na potworki. Ponieważ trójkąt równoboczny o boku $n=12k$ można podzielić na $k^2$ trójkątów równobocznych o boku 12, więc wystarczy wskazać podział trójkąta równobocznego o boku 12 na potworki. Taki podział wskazany jest na rys. 3.

Odpowiedź: Trójkąt równoboczny o boku $n$ można podzielić na potworki wtedy i tylko wtedy, gdy liczba $n$ jest podzielna przez 12.

XVIII ZMPB - Zadanie 8

Zawody matematyczne:

XVIII ZMPB, 2007

Nazwijmy zbiór $A$ liczb całkowitych nieizolowanym, jeżeli dla każdego $a\in A$ przynajmniej jedna z liczb $a-1$ , $a+1$ także należy do $A$ . Udowodnić, że liczba pięcioelementowych nieizolowanych podzbiorów zbioru $\{1,2,\ldots,n\}$ wynosi $(n-4)^2$ .

Rozwiązanie

Zauważmy, że pięcioelementowe zbiory nieizolowane dzielą się na dwie kategorie:

Zbiory postaci $\{a,a+1,a+2,a+3,a+4\}$ dla pewnej liczby całkowitej $a$ .
Zbiory postaci $\{a,a+1,a+2\}\cup\{b,b+1\}$ , gdzie $a$ i $b$ są takimi liczbami całkowitymi, że każda z liczb $a$ , $a+1$ , $a+2$ jest różna od $b-1$ , $b$ , $b+1$ , $b+2$ .

Podzbiory nieizolowane postaci $\{a,a+1,a+2,a+3,a+4\}\subseteq\{1,2,\ldots,n\}$ otrzymujemy dla $a=1,2,\ldots,n-4$ . Jest więc $n-4$ takich podzbiorów.

Podzbiory nieizolowane postaci $\{a,a+1,a+2\}\cup\{b,b+1\}\subseteq\{1,2,\ldots,n\}$ , dla których $a<b$ , otrzymujemy wybierając najpierw liczbę $b\in\{1,2,\ldots,n-1\}$ , a następnie liczbę $a\in\{1,2,\ldots,b-4\}$ . Musi przy tym być spełniona nierówność $b\ge 4$ ; w przeciwnym razie nie będziemy bowiem mogli dobrać żadnej wartości $a$ . Ponadto przy ustalonej wartości $b\ge 4$ możemy wybrać liczbę $a$ na $b-4$ sposobów. Sumując liczbę $b-4$ dla wartości $b=4,5,\ldots,n-1$ otrzymamy $0+1+2+\ldots+(n-5)=\xfrac{1}{2}(n-5)(n-4)$ .

Rozumując w analogiczny sposób łatwo stwierdzamy, że również liczba nieizolowanych podzbiorów postaci $\{a,a+1,a+2\}\cup\{b,b+1\}\subseteq\{1,2,\ldots,n\}$ , w których $a>b$ , wynosi $\frac{1}{2}(n-5)(n-4)$ . Stąd wniosek, że liczba wszystkich nieizolowanych pięcioelementowych podzbiorów zbioru $\{1,2,\ldots,n\}$ jest równa

$ (n-4)+\xfrac{1}{2}(n-5)(n-4)+\xfrac{1}{2}(n-5)(n-4)=(n-4)^2. $

XVIII ZMPB - Zadanie 9

Zawody matematyczne:

XVIII ZMPB, 2007

W pewnym stowarzyszeniu należy wybrać zarząd. Każdy członek wskazał 10 kandydatów do zarządu, ale będzie zadowolony, jeżeli przynajmniej jeden z nich znajdzie się w zarządzie. Dla dowolnych sześciu członków stowarzyszenia można utworzyć dwuosobowy zarząd, zadowalający wszystkich sześciu. Dowieść, że można wybrać 10-osobowy zarząd, zadowalający wszystkich członków stowarzyszenia.

Rozwiązanie

Niech $a$ będzie jednym z członków stowarzyszenia, a $A=\{a_1,a_2,\ldots,a_{10}\}$ zbiorem jego kandydatów do zarządu. Jeżeli zbiór kandydatów wskazanych przez każdego innego członka ma niepuste przecięcie ze zbiorem $A$ , wówczas zarząd złożony z osób $a_1$ , $a_2$ , $\ldots$ , $a_{10}$ będzie zadowalał wszystkich członków stowarzyszenia.

Przyjmujemy w związku z tym w dalszej częsci rozumowania, że istnieje taki członek stowarzyszenia $b$ , że zbiór $B=\{b_1,b_2,\ldots,b_{10}\}$ wskazanych przezeń kandydatów jest rozłączny ze zbiorem $A$ .

Oznaczmy

$ \begin{split} A_1=\{a_1,a_2,\ldots,a_5\},\quad&\quad A_2=\{a_6,a_7,\ldots,a_{10}\},\\ B_1=\{b_1,b_2,\ldots,b_5\},\quad&\quad B_2=\{b_6,b_7,\ldots,b_{10}\}. \end{split} $

Udowodnimy, że przynajmniej jeden z 10-osobowych zbiorów

$ A_1\cup B_1,\qquad A_1\cup B_2,\qquad A_2\cup B_1,\qquad A_2\cup B_2 $

tworzy zarząd zadowalający wszystkich członków stowarzyszenia.

Przypuśćmy, że tak nie jest; istnieją więc członkowie $x$ , $y$ , $z$ , $t$ , niezadowoleni odpowiednio z zarządów $A_1\cup B_1$ , $A_1\cup B_2$ , $A_2\cup B_1$ , $A_2\cup B_2$ . Zgodnie z założeniami istnieje zarząd złożony z dwóch osób $v$ i $w$ , który zadowala każdego z sześciu członków $a$ , $b$ , $x$ , $y$ , $z$ , $t$ . Ponieważ zarząd ten zadowala członków $a$ i $b$ , więc jedna z osób $v$ , $w$ należy do zbioru $A$ , a druga - do zbioru $B$ . Dla ustalenia oznaczeń niech $v\in A$ oraz $w\in B$ . Zatem

$ v\in A_i\quad\hbox{oraz}\quad w\in B_j\qquad\hbox{dla pewnych }i,j\in\{1,2\}. $

Wynika stąd, że zbiór $\{v,w\}$ zawiera się w zbiorze $A_i\cup B_j$ . Jednak zarząd $A_i\cup B_j$ nie zadowala jednego z członków $x$ , $y$ , $z$ , $t$ , wbrew temu, że każdy z tych czterech członków jest zadowolony z zarządu $\{v,w\}$ .

Otrzymaliśmy sprzeczność, z której wynika teza zadania.

XVIII ZMPB - Zadanie 10

Zawody matematyczne:

XVIII ZMPB, 2007

Dana jest tablica $18\times 18$ , której każde pole może być białe albo czarne. Początkowo wszystkie pola są białe. Możemy wykonywać następującą operację: wybieramy kolumnę lub wiersz i zmieniamy kolory wszystkich pól w tej kolumnie lub wierszu. Czy wykonując wielokrotnie taką operację możemy otrzymać tablicę, w której będzie dokładnie 16 czarnych pól?

Rozwiązanie

Odpowiedź: Nie można.

Zauważmy przede wszystkim, że jeżeli wykonując wielokrotnie opisaną operację wybierzemy dwukrotnie ten sam wiersz lub tę samą kolumnę, to uzyskamy taką samą tablicę, jaką uzyskalibyśmy nie wybierając w ogóle tego wiersza lub tej kolumny. Wobec tego wystarczy rozpatrywać przypadek, w którym każdy wiersz i każda kolumna została wybrana najwyżej raz.

Przypuśćmy, że udało nam się uzyskać tablicę, w której dokładnie 16 pól jest czarnych.

Ponieważ liczba wszystkich wierszy jest równa 18, więc istnieje wiersz $W$ , w którym wszystkie pola są białe. Załóżmy, że przy wykonywaniu ciągu dozwolonych operacji wybraliśmy wiersz $W$ . Skoro początkowo wszystkie pola położone w wierszu $W$ były białe oraz po zakończeniu operacji wszystkie te pola są również białe, więc musiała zostać wybrana każda kolumna. Wówczas jednak każdy wiersz składałby się wyłącznie z białych albo wyłącznie z czarnych pól; łączna liczba tych ostatnich byłaby zatem podzielna przez 18.

Z drugiej strony, jeżeli podczas wykonywania dopuszczalnych operacji nie wybraliśmy wiersza $W$ , to nie mogła zostać wybrana żadna kolumna - w przeciwnym bowiem razie pole stojące na przecięciu tej kolumny z wierszem $W$ byłoby czarne. To jednak oznacza, że we wszystkich wykonanych operacjach wybierany był wiersz, różny od wiersza $W$ . Podobnie jak poprzednio, wynika stąd, że każdy wiersz składa się tylko z białych albo tylko z czarnych pól, więc liczba czarnych pól nie może być równa 16. Otrzymana sprzeczność kończy rozwiązanie.

XVIII ZMPB - Zadanie 11

Zawody matematyczne:

XVIII ZMPB, 2007

W trójkącie $ABC$ odcinki $AD$ , $BE$ i $CF$ są wysokościami. Punkty $P$ , $Q$ , $R$ i $S$ spełniają następujące warunki:

$P$ jest środkiem okręgu opisanego na trójkącie $ABC$ .
Długości odcinków $PQ$ , $QR$ i $RS$ są równe promieniowi okręgu opisanego na trójkącie $ABC$ .
Odcinek zorientowany $PQ$ ma ten sam kierunek i zwrot, co odcinek zorientowany $AD$ . Podobnie, odcinek $QR$ ma ten sam kierunek i zwrot, co $BE$ , zaś odcinek $RS$ ma ten sam kierunek i zwrot, co $CF$ .

Wykazać, że punkt $S$ jest środkiem okręgu wpisanego w trójkąt $ABC$ .

Rozwiązanie

Punkt $P$ jest środkiem okręgu opisanego na trójkącie $ABC$ , a długość odcinka $PQ$ jest równa promieniowi tego okręgu. Zatem punkt $Q$ leży na tym okręgu. Ponadto $PB=PC$ oraz prosta $PQ$ jest prostopadła do boku $BC$ . Jest ona więc jego symetralną, a to oznacza, że punkt $Q$ jest środkiem łuku $BC$ okręgu opisanego na trójkącie $ABC$ nie zawierającego punktu $A$ (rys. 4). Wynika stąd, że punkt $Q$ leży na dwusiecznej kąta $\measuredangle CAB$ .

Udowodnimy, że punkt $S$ również leży na dwusiecznej kąta $\measuredangle CAB$ . W tym celu wystarczy wykazać, że prosta $QS$ jest równoległa do dwusiecznej tego kąta. Trójkąt $QRS$ jest równoramienny, więc stwierdzenie to sprowadza się do wykazania, że dwusieczne kątów $\measuredangle QRS$ i $\measuredangle CAB$ są prostopadłe. To zaś bezpośrednio wynika z faktu, że ramiona tych kątów są prostopadłe ( $QR\perp CA$ oraz $RS\perp AB$ ).

Wykażemy jeszcze, że punkt $S$ leży także na dwusiecznej kąta $\measuredangle ABC$ . Stąd otrzymamy, że punkt $S$ jest środkiem okręgu wpisanego w trójkąt $ABC$ .

Niech $T$ będzie takim punktem płaszczyzny, że czworokąt $PQRT$ jest równoległobokiem. Wówczas $PT\parallel QR\parallel BE$ oraz $TR\parallel PQ\parallel AD$ (równoległości te traktujemy jako równości kierunków i zwrotów odpowiednich odcinków skierowanych). Zatem odcinki skierowane $PT$ , $TR$ , $RS$ , których długości są równe promieniowi okręgu opisanego na trójkącie $ABC$ , mają odpowiednio te same kierunki i zwroty, co odcinki skierowane $BE$ , $AD$ , $CF$ . Rozumując analogicznie jak w początkowej części rozwiązania dostajemy stąd, że punkt $S$ leży na dwusiecznej kąta $\measuredangle ABC$ , a tego dowodziliśmy.

XVIII ZMPB - Zadanie 12

Zawody matematyczne:

XVIII ZMPB, 2007

Punkt $M$ leży na tym łuku $AB$ okręgu opisanego na trójkącie $ABC$ , który nie zawiera punktu $C$ . Załóżmy, że rzuty prostokątne punktu $M$ na proste $AB$ i $BC$ leżą na samych bokach, a nie na ich przedłużeniach. Oznaczmy te rzuty odpowiednio przez $X$ i $Y$ . Niech $K$ i $N$ będą odpowiednio środkami odcinków $AC$ i $XY$ . Dowieść, że $\measuredangle MNK=90^\circ$ .

Rozwiązanie

Z równości kątów (rys. 5)

$\measuredangle MAX=\measuredangle MCB\qquad\hbox{oraz}\qquad \measuredangle MXA=\measuredangle MYC=90^\circ$

wynika, że trójkąty $MXA$ i $MYC$ są podobne (cecha kąt-kąt-kąt). Zatem

$ \measuredangle AMX=\measuredangle CMY,\qquad\hbox{czyli}\qquad \measuredangle AMC=\measuredangle XMY $

oraz

$ {MA\over MC}={MX\over MY}. $

Dwie ostatnie zależności implikują, że trójkąty $MCA$ i $MYX$ są podobne. Punkty $K$ i $N$ są środkami odpowiadających sobie boków w tych trójkątach, zatem trójkąty $MKA$ i $MNX$ również są podobne. Stąd otrzymujemy równość stosunków

$ {MN\over MK}={MX\over MA} $

oraz równość kątów

$ \measuredangle NMX=\measuredangle KMA,\qquad\hbox{czyli}\qquad \measuredangle NMK=\measuredangle XMA. $

Z dwóch ostatnich równości wnioskujemy, że trójkąty $AMX$ i $KMN$ są podobne. Skutkiem tego $\measuredangle MNK=\measuredangle MXA=90^\circ$ , co należało wykazać.

XVIII ZMPB - Zadanie 13

Zawody matematyczne:

XVIII ZMPB, 2007

Niech $t_1$ , $t_2$ , $\ldots$ , $t_k$ będą różnymi prostymi w przestrzeni ( $k>1$ ). Udowodnić, że istnieją takie punkty $P_i$ na $t_i$ ( $i=1,2,\ldots,k$ ), że $P_{i+1}$ jest rzutem prostokątnym $P_i$ na prostą $t_{i+1}$ ( $i=1,2,\ldots,k-1$ ), a $P_1$ jest rzutem prostokątnym $P_k$ na prostą $t_1$ .}

Rozwiązanie

Niech $\pi_1$ będzie odwzorowaniem o dziedzinie $t_1$ i przeciwdziedzinie $t_2$ , które dowolnemu punktowi $P\in t_1$ przyporządkowuje punkt $\pi_1(P)\in t_2$ będący rzutem prostokątnym punktu $P$ na prostą $t_2$ . Analogicznie określamy odwzorowania $\pi_2:t_2\to t_3$ , $\pi_3:t_3\to t_4$ , $\ldots$ , $\pi_k:t_k\to t_1$ .

Przy tych oznaczeniach tezę zadania można sformułować następująco: istnieją takie punkty $P_1$ , $P_2$ , $\ldots$ , $P_k$ leżące odpowiednio na $t_1$ , $t_2$ , $\ldots$ , $t_k$ , że

$ \pi_1(P_1)=P_2,\quad \pi_2(P_2)=P_3,\quad\ldots\quad \pi_k(P_k)=P_1. (1) \qquad $

Niech $\pi$ oznacza złożenie $\pi_k\circ\pi_{k-1}\circ\ldots\circ \pi_2\circ\pi_1$ . Zatem $\pi$ jest odwzorowaniem $\pi:t_1\to t_1$ . Wykażemy, że odwzorowanie $\pi$ ma punkt stały, czyli że istnieje punkt $P_1\in t_1$ , dla którego zachodzi równość $\pi(P_1)=P_1$ .

Wprowadźmy na każdej prostej $t_i$ ( $i=1,2,\ldots,k$ ) strukturę osi liczbowej w taki sposób, by na każdej z tych prostych punkty $0$ i $1$ były punktami przestrzeni odległymi od siebie o $1$ . Zatem punktom każdej z prostych $t_1$ i $t_2$ odpowiadają wzajemnie jednoznacznie wszystkie liczby rzeczywiste; w języku tych liczb odwzorowanie $\pi_2$ można opisać wzorem $x\mapsto ax+b$ , gdzie współczynnik $a$ jest cosinusem kąta pomiędzy wektorem zawartym w prostej $t_1$ o początku $0$ i końcu $1$ a wektorem zawartym w prostej $t_2$ o początku $0$ i końcu $1$ . Wynika stąd, że $|a|\le 1$ , przy czym równość $|a|=1$ oznacza, że proste $t_1$ i $t_2$ są równoległe.

Rozpatrując analogicznie pozostałe odwzorowania $\pi_2$ , $\pi_3$ , $\ldots$ , $\pi_k$ oraz zauważając, że złożenie przekształceń postaci $x\to ax+b$ jest również przekształceniem tej postaci, przy czym odpowiednie współczynniki $a$ mnożą się, dochodzimy do wniosku, że odwzorowanie $\pi:t_1\to t_1$ daje się opisać wzorem $x\to Ax+B$ . Przy tym $|A|\le 1$ , a równość $A=1$ jest możliwa tylko w przypadku, gdy wszystkie proste $t_1$ , $t_2$ , $\ldots$ , $t_k$ są równoległe.

Przypuśćmy, że $A=1$ , czyli proste $t_1$ , $t_2$ , $\ldots$ , $t_k$ są równoległe. Wybierzmy dowolny punkt $P\in t_1$ i rozważmy jego rzut prostokątny $P'$ na prostą $t_2$ . Punkty $P$ i $P'$ leżą wówczas na jednej płaszczyźnie prostopadłej do prostych $t_1$ , $t_2$ . Ponadto punkt $P''$ będący rzutem prostokątnym punktu $P'$ na prostą $t_3$ leży na tej płaszczyźnie, rzut prostokątny punktu $P''$ na prostą $t_4$ leży w tej płaszczyźnie itd.; to zaś oznacza, że $\pi$ jest odwzorowaniem stałym.

Jeżeli natomiast $A\ne 1$ , to równanie $x=Ax+B$ ma dokładnie jedno rozwiązanie, mianowicie liczbę $x=B/(1-A)$ . Punkt $P_1$ odpowiadający tej liczbie na prostej $t_1$ jest wówczas punktem stałym odwzorowania $\pi$ .

Zatem odwzorowanie $\pi:t_1\to t_1$ ma punkt stały $P_1$ . Określmy

$ P_2=\pi_1(P_1),\quad P_3=\pi_2(P_2),\quad\ldots,\quad P_k=\pi_{k-1}(P_{k-1}); $

by sprawdzić, że wszystkie równości (1) są spełnione, brakuje tylko zależności $P_1=\pi_k(P_k)$ . Jest ona jednak prawdziwa, gdyż

$ \begin{split} \pi_k(P_k)&=\pi_k(\pi_{k-1}(P_{k-1}))=\ldots= \pi_k(\pi_{k-1}(\ldots \pi_2(\pi_1(P_1))\ldots))=\cr &=(\pi_k\circ\ldots\circ\pi_2\circ\pi_1)(P_1)=\pi(P_1)=P_1. \end{split} $

To kończy rozwiązanie.

XVIII ZMPB - Zadanie 14

Zawody matematyczne:

XVIII ZMPB, 2007

W czworokącie wypukłym $ABCD$ zachodzi równość $\measuredangle ADC=90^\circ$ . Punkty $E$ i $F$ są rzutami prostokątnymi punktu $B$ odpowiednio na proste $AD$ i $AC$ . Załóżmy, że punkt $F$ leży między $A$ i $C$ , punkt $A$ leży między $D$ i $E$ , zaś prosta $EF$ przechodzi przez środek odcinka $BD$ . Dowieść, że na czworokącie $ABCD$ można opisać okrąg.

Rozwiązanie

Trójkąt $DEB$ jest prostokątny (gdyż $\measuredangle DEB=90^\circ$ ), zatem jeżeli prosta $EF$ , zawierająca wierzchołek kąta prostego tego trójkąta, przechodzi przez środek odcinka $BD$ - przeciwprostokątnej w tym trójkącie, to ma miejsce równość kątów $\measuredangle FEB=\measuredangle DBE$ (rys. 6). Proste $BE$ i $CD$ są równoległe, więc $\measuredangle DBE=\measuredangle CDB$ . Wobec tego otrzymujemy $\measuredangle FEB=\measuredangle CDB$ .

Z drugiej strony, kąty $\measuredangle AEB$ i $\measuredangle AFB$ są kątami prostymi, zatem punkty $A$ , $E$ , $B$ , $F$ leżą w tej kolejności na jednym okręgu i zachodzą równości

$ \measuredangle FEB=\measuredangle FAB=\measuredangle CAB. $

Łącząc to z wcześniej uzyskaną zależnością $\measuredangle FEB=\measuredangle CDB$ widzimy, że $\measuredangle CDB=\measuredangle CAB$ , a to oznacza, że na czworokącie $ABCD$ można opisać okrąg.

XVIII ZMPB - Zadanie 15

Zawody matematyczne:

XVIII ZMPB, 2007

Okrąg wpisany w trójkąt $ABC$ jest styczny do boku $AC$ w punkcie $D$ . Inny okrąg przechodzi przez punkt $D$ i jest styczny do półprostych $BC$ i $BA$ - do drugiej z nich w punkcie $A$ . Obliczyć stosunek $AD/DC$ .

Rozwiązanie

Niech $P$ i $R$ będą odpowiednio punktami styczności okręgu wpisanego w trójkąt $ABC$ z bokami $AB$ i $BC$ (rys. 7) oaz niech $S$ będzie punktem styczności drugiego z danych w treści zadania okręgów do prostęj $BC$ .

Oznaczmy

$ x=CD,\quad y=AD. $

Korzystając z równości odcinków stycznych dostajemy

$ CS=RS-CR=PA-CD=DA-CD=y-x, $

co prowadzi do równości

$ (y-x)^2=CS^2=CD\cdot CA=x(x+y). $

Z powyższej równości otrzymujemy $y^2-2yx+x^2=x^2+xy$ , czyli $y^2=3xy$ . Liczba $y=AD$ jest różna od zera, więc $y=3x$ i ostatecznie $AD/DC=y/x=3$ .

XVIII ZMPB - Zadanie 16

Zawody matematyczne:

I OM, 1949-1950

Niech $a$ i $b$ będą takimi liczbami wymiernymi, że

$ s=a+b=a^2+b^2. $

Wykazać, że liczbę $s$ można zapisać w postaci ułamka, którego mianownik jest względnie pierwszy z liczbą 6.

Rozwiązanie

Zapiszmy

$ a={m\over k},\qquad b={n\over k}, $

gdzie $m$ , $n$ , $k$ są dodatnimi liczbami całkowitymi oraz $k$ jest najmniejszym możliwym wspólnym mianownikiem. Wynika stąd w szczególności, że liczby $m$ , $n$ , $k$ nie mają wspólnego dzielnika większego od 1.

Na mocy warunków zadania otrzymujemy

$ s=a+b={m+n\over k}=a^2+b^2={m^2+n^2\over k^2}, $

skąd dostajemy równość

$ (1) \qquad (m+n)k=m^2+n^2. $

Z równości tej wynika, że liczby $k$ i $m$ są względnie pierwsze - ich ewentualny wspólny dzielnik pierwszy $p$ dzieliłby lewą stronę oraz liczbę $m^2$ , więc mielibyśmy $p\,|\,n^2$ , lecz płynący stąd wniosek, że $p$ jest wspólnym dzielnikiem liczb $k$ , $m$ , $n$ , przeczyłby wcześniejszym założeniom. Analogicznie liczby $k$ i $n$ są względnie pierwsze.

Ponieważ liczba $s$ daje się zapisać jako ułamek o mianowniku $k$ , więc wystarczy udowodnić, że liczby $k$ i 6 są względnie pierwsze.

Przypuśćmy, że $2\,|\,k$ . Wówczas liczby $m$ i $n$ nie są podzielne przez 2, więc ich kwadraty dają resztę 1 z dzielenia przez 4, co daje $m^2+n^2\equiv 2\mod{4}$ . Jest to niemożliwe - lewa strona równości (1) jest podzielna przez 4, gdyż jest iloczynem dwóch parzystych czynników.

Przypuśćmy, że $3\,|\,k$ . Liczby $m$ i $n$ są zatem niepodzielne przez 3; w efekcie ich kwadraty dają resztę 1 z dzielenia przez 3 oraz $m^2+n^2\equiv 2\mod{3}$ . To daje sprzeczność, gdyż lewa strona zależności (1) jest podzielna przez 3.

Dowiedliśmy więc, że $k$ nie dzieli się przez 2 ani przez 3, skąd teza.

XVIII ZMPB - Zadanie 17

Zawody matematyczne:

XVIII ZMPB, 2007

Niech $x$ , $y$ , $z$ będą takimi dodatnimi liczbami całkowitymi, że liczba

$ {x+1\over y}+{y+1\over z}+{z+1\over x} $

jest całkowita. Niech $d$ oznacza największy wspólny dzielnik liczb $x$ , $y$ oraz $z$ . Udowodnić, że

$ d\le\sqrt[3]{xy+yz+zx}. $

Rozwiązanie

Na mocy założeń zadania istnieją takie liczby całkowite $a$ , $b$ , $c$ , że

$ x=da,\quad y=db,\quad z=dc. $

Liczba

$ \begin{split} {x+1\over y}+{y+1\over z}+{z+1\over x}&= {x^2z+y^2x+z^2y+xz+yx+zy\over xyz}=\\ &={d^3(a^2c+b^2a+c^2b)+d^2(ac+cb+ba)\over d^3abc} \end{split} $

jest całkowita, zatem licznik ułamka stojącego po prawej stronie powyższej równości jest liczbą podzielną przez $d^3$ . Wynika stąd, że liczba $ac+cb+ba$ jest podzielna przez $d$ . Otrzymujemy więc

$ d\le ac+cb+ba={xy+yz+zx\over d^2},\qquad\hbox{czyli}\qquad d^3\le xy+yz+zx, $

co jest równoznaczne z tezą zadania.

XVIII ZMPB - Zadanie 18

Zawody matematyczne:

XVIII ZMPB, 2007

Niech $a$ , $b$ , $c$ , $d$ będą takimi liczbami całkowitymi różnymi od zera, że jedyną czwórką liczb całkowitych $(x,y,z,t)$ spełniającą równanie

$ ax^2+by^2+cz^2+dt^2=0 $

jest $x=y=z=t=0$ . Czy wynika stąd, że liczby $a$ , $b$ , $c$ , $d$ mają jednakowy znak?

Rozwiązanie

Odpowiedź: Nie.

Udowodnimy na przykład, że liczby $(a,b,c,d)=(1,1,-3,-3)$ spełniają założenia zadania. Aby to uczynić, przypuśćmy, że liczby całkowite $x$ , $y$ , $z$ , $t$ są rozwiązaniem równania

$ (1) \qquad x^2+y^2-3z^2-3t^2=0. $

Liczba $x^2+y^2=3(z^2+t^2)$ jest wówczas podzielna przez 3. Ponieważ kwadrat liczby całkowitej podzielnej przez 3 jest podzielny przez 3, a kwadrat liczby całkowitej niepodzielnej przez 3 daje resztę 1 z dzielenia przez 3, więc suma $x^2+y^2$ może być podzielna przez 3 jedynie wtedy, gdy liczby $x$ i $y$ są podzielne przez 3. W tej sytuacji liczba $x^2+y^2$ jest podzielna przez 9, co pociąga podzielność liczby $z^2+t^2$ przez 3. W konsekwencji liczby $z$ i $t$ są również podzielne przez 3.

Zatem dowolne całkowite rozwiązanie równania (1) składa się z liczb podzielnych przez 3. Jest to równanie jednorodne: jeżeli liczby $x$ , $y$ , $z$ , $t$ są jego rozwiązaniem, to liczby ${1\over 3}x$ , ${1\over 3}y$ , ${1\over 3}z$ , ${1\over 3}t$ również. Gdyby więc istniało rozwiązanie, w którym któraś z liczb całkowitych $x$ , $y$ , $z$ , $t$ byłaby niezerowa, to dzieląc wszystkie te liczby przez odpowiednią potęgę liczby 3 otrzymalibyśmy rozwiązanie w liczbach całkowitych, nie wszystkich podzielnych przez 3, a jak wcześniej udowodniliśmy - takich rozwiązań nie ma. Wobec tego jedynym rozwiązaniem równania (1) w liczbach całkowitych jest $x=y=z=t=0$ .

XVIII ZMPB - Zadanie 19

Zawody matematyczne:

XVIII ZMPB, 2007

Dane są dodatnie liczby całkowite $r$ i $k$ . Wszystkie dzielniki pierwsze liczby $r$ są większe od 50.

Dodatnią liczbę całkowitą, której zapis dziesiętny (bez zer początkowych) ma co najmniej $k$ cyfr, nazwiemy ładną, jeżeli każdy ciąg $k$ kolejnych cyfr tego zapisu przedstawia liczbę (być może z zerami początkowymi) podzielną przez $r$ .

Dowieść, że jeżeli istnieje nieskończenie wiele liczb ładnych, to liczba $10^k-1$ też jest ładna.

Rozwiązanie

Z warunków zadania wynika, że istnieje liczba ładna, której zapis dziesiętny składa się z przynajmniej $10k+1$ cyfr. Niech $c_1$ , $c_2$ , $\ldots$ , $c_{10k+1}$ będą początkowymi cyframi tej liczby.

Na podstawie określenia liczby ładnej podzielne przez $r$ są liczby

$ \begin{split} a & =10^{k-1}c_1+10^{k-2}c_2+\ldots+10c_{k-1}+c_k, \cr b & =10^{k-1}c_2+10^{k-2}c_3+\ldots+10c_k+c_{k+1}. \end{split} $

Wynika stąd, że liczba

$ 10a-b=10^kc_1-c_{k+1} $

także jest podzielna przez $r$ . Przyjmując oznaczenie $d_i=c_{ik+1}$ ( $i=0,1,\ldots,10$ ) dowodzimy analogicznie, iż spełnione są podzielności

$ r\,|\,10^kd_i-d_{i+1}\qquad\hbox{dla }i=0,1,\ldots,9. (1) \qquad $

Ciąg $d_0$ , $d_1$ , $\ldots$ , $d_{10}$ składa się z 11 cyfr, więc pewne dwie cyfry w tym ciągu muszą być równe. Zatem istnieją takie wskaźniki $0\le i<j\le 10$ , że cyfry $d_i$ , $d_{i+1}$ , $\ldots$ , $d_{j-1}$ są parami różne oraz $d_i=d_j$ . Na mocy związków (1) liczba

$ \begin{split}(10^kd_i & -d_{i+1})+(10^kd_{i+1}-d_{i+2})+\ldots+(10^kd_{j-1}-d_j)= \cr & =(10^kd_i-d_{i+1})+(10^kd_{i+1}-d_{i+2})+\ldots+(10^kd_{j-1}-d_i)= \cr & =(10^k-1)(d_i+d_{i+1}+\ldots+d_{j-1}) \end{split} $

jest podzielna przez $r$ . Jednakże czynnik $d_i+d_{i+1}+\ldots+d_{j-1}$ jest sumą różnych cyfr, zatem nie przekracza liczby $0+1+2+\ldots+9=45$ i wobec tego jest względnie pierwszy z liczbą $r$ . W konsekwencji $10^k-1$ jest $k$ -cyfrową liczbą podzielną przez $r$ , skąd wynika teza zadania.

XVIII ZMPB - Zadanie 20

Zawody matematyczne:

XVIII ZMPB, 2007

Niech $a$ i $b$ będą takimi dodatnimi liczbami całkowitymi, że $b<a$ oraz liczba $a^3+b^3+ab$ jest podzielna przez $ab(a-b)$ . Udowodnić, że $ab$ jest sześcianem liczby całkowitej.

Rozwiązanie

Niech $d$ oznacza największy wspólny dzielnik liczb $a$ i $b$ . Wówczas

$ a=dk, \qquad b=dl, $

gdzie $k$ i $l$ są względnie pierwszymi dodatnimi liczbami całkowitymi. Na mocy założeń zadania liczba

$ {a^3+b^3+ab\over ab(a-b)}= {(dk)^3+(dl)^3+d^2kl\over d^3kl(k-l)}= {dk^3+dl^3+kl\over dkl(k-l)} $

jest całkowita. Licznik ułamka stojącego po prawej stronie jest więc liczbą podzielną przez $l$ i wobec tego liczba $dk^3$ jest również podzielna przez $l$ . Liczby $k$ i $l$ są jednak względnie pierwze, zatem otrzymujemy podzielność $l\,|\,d$ . Analogicznie uzyskujemy $k\,|\,d$ i korzystając ponownie z względnej pierwszości liczb $k$ i $l$ stwierdzamy, że liczba $d$ jest podzielna przez $kl$ .

Istnieje więc taka dodatnia liczba całkowita $t$ , że $d=tkl$ . Liczba

$ {a^3+b^3+ab\over ab(a-b)}= {dk^3+dl^3+kl\over dkl(k-l)}= {tk^4l+tkl^4+kl\over tkl(k-l)}= {tk^3+tl^3+1\over t(k-l)} $

jest całkowita; w konsekwencji licznik ostatniego ułamka jest liczbą podzielną przez $t$ , co jest możliwe jedynie dla $t=1$ . Stąd kolejno otrzymujemy: $d=kl$ , $a=dk=k^2l$ oraz $b=dl=kl^2$ . W efekcie $ab=(kl)^3$ jest sześcianem liczby całkowitej, co kończy rozwiązanie.