Czesko-Polsko-Słowackie Zawody Matematyczne

Czesko–Polsko–Słowackie Zawody Matematyczne te mają charakter nieoficjalny i stanowią formę treningu dla zawodników
biorących udział w Międzynarodowej Olimpiadzie Matematycznej [1]. Formuła
zawodów jest taka sama, jak w przypadku MOM: w ciagu dwóch
dni zawodnicy rozwiązują sześć zadań — po trzy zadania podczas 4, 5 godziny każdego z dwóch dni.

IX CPS

Zawody matematyczne:

IX CPS, 2009

Zadania z IX Czesko-Polsko-Słowackich Zawodów Matematycznych

Załącznik	Wielkość
IX CPS - Zadania z rozwiązaniami [2]	175.22 KB

IX CPS - Zadanie 1

Zawody matematyczne:

IX CPS, 2009

Niech $\mathbb R_+$ oznacza zbiór liczb rzeczywistych dodatnich. Znaleźć wszystkie funkcje $f:\mathbb R_+\to\mathbb R_+$ , spełniające dla dowolnych $x,y\in\mathbb R_+$ zależność

$ (1+yf(x))(1-yf(x+y))=1. $

Rozwiązanie

Niech $f(1)=a>0$ . Podstawiając $x=1$ i przekształcając równanie z treści zadania, otrzymujemy

$ (1+ay)\left(1-yf(y+1)\right)=1,\\ ay-yf(y+1)(1+ay)=0,\\ f(y+1)=\frac a{1+ay}. $

Następnie ponownie przekształcamy równanie z treści zadania, podstawiając $y=1$ i $f(x+1)=a/(1+ax)$ :

$ \begin{split} \left(1+f(x)\right)\left(1-\frac a{1+ax}\right)&=1,\\ f(x)\cdot\frac{1+ax-a}{1+ax}&=\frac a{1+ax},\\ f(x)&=\frac a{1+ax-a}=\frac1{x+\frac1a-1}=\frac1{x+c}, \end{split} $

gdzie $c=1/a-1$ . Wiadomo, że $f(x)>0$ dla wszystkich $x>0$ , więc $x+c>0$ dla $x>0$ i stąd $c\geq0$ .

Na koniec sprawdzimy, że funkcja $f(x)=1/(x+c)$ spełnia warunki zadania dla dowolnego $c\geq0$ :

$ \left(1+\frac y{x+c}\right)\left(1-\frac y{x+y+c}\right)=\frac{x+c+y}{x+c}\cdot\frac{x+y+c-y}{x+y+c}=1. $

IX CPS - Zadanie 2

Zawody matematyczne:

IX CPS, 2009

Niech $a,k$ będą liczbami całkowitymi dodatnimi. Ciąg $(a_n)_{n=1}^\infty$ definiujemy następująco:

$ a_1=a\quad\text{oraz}\quad a_{n+1}=a_n+k\varrho(a_n),\quad\text{dla }n=1,2,\dots, $

gdzie $\varrho(m)$ oznacza iloczyn cyfr liczby $m$ w zapisie dziesiętnym (np. $\varrho(413)=12$ , $\varrho(308)=0$ ). Udowodnić, że istnieją takie liczby całkowite dodatnie $a$ i $k$ , że ciąg $(a_n)_{n=1}^\infty$ przyjmuje dokładnie 2009 różnych wartości.

Rozwiązanie

Zauważmy, że ciąg $(a_n)_{n=1}^\infty$ jest rosnący do momentu pojawienia się pierwszego wyrazu, w którego rozwinięciu dziesiętnym jest 0 i od tego miejsca ciąg jest stały. Wskażemy zatem takie $a$ i $k$ , że 0 pojawi się po raz pierwszy w rozwinięciu $a_{2009}$ .

Niech

$ a=6\underbrace{11\dots 1}_{2007}\qquad\text{i}\qquad k=\underbrace{33\dots3}_{2007}4=\frac16\cdot2\underbrace{00\dots 0}_{2007}4. $

Wtedy

$ \begin{array}{lll} a_1=6\underbrace{11\dots 1}_{2007}, & \varrho(a_1)=6, & k\varrho(a_1)=2\underbrace{00\dots 0}_{2007}4,\\ a_2=26\underbrace{11\dots 1}_{2006}5, & \varrho(a_2)=60, & k\varrho(a_2)=2\underbrace{00\dots 0}_{2007}40,\\ a_3=226\underbrace{11\dots 1}_{2005}55, & \varrho(a_3)=600, & k\varrho(a_3)=2\underbrace{00\dots 0}_{2007}400,\\ & \,\vdots &&&&\\ a_{i+1}=\underbrace{22\dots2}_i6\underbrace{11\dots 1}_{2007-i}\underbrace{55\dots5}_i, & \varrho(a_{i+1})=6\underbrace{0\dots 0}_i, & k\varrho(a_{i+1})=2\underbrace{00\dots 0}_{2007}4\underbrace{00\dots 0}_i,\\ & \,\vdots &&&&\\ a_{2007}=\underbrace{22\dots2}_{2006}61\underbrace{55\dots5}_{2006}, & \varrho(a_{2007})=6\underbrace{0\dots 0}_{2006}, & k\varrho(a_{2007})=2\underbrace{00\dots 0}_{2007}4\underbrace{00\dots 0}_{2006},\\ a_{2008}=\underbrace{22\dots2}_{2007}6\underbrace{55\dots5}_{2007}, & \varrho(a_{2008})=6\underbrace{0\dots 0}_{2007}, & k\varrho(a_{2008})=2\underbrace{00\dots 0}_{2007}4\underbrace{00\dots 0}_{2007},\\ a_{2009}=\underbrace{22\dots2}_{2007}30\underbrace{55\dots5}_{2007}, & \varrho(a_{2009})=0, & k\varrho(a_{2009})=0 \end{array} $

oraz $a_n=a_{2009}$ dla wszystkich $n>2009$ . Zatem dla powyższych $a$ i $k$ ciąg spełnia warunki zadania.

IX CPS - Zadanie 3

Zawody matematyczne:

IX CPS, 2009

Niech $k$ będzie okręgiem dopisanym do trójkąta $ABC$ , stycznym do boku $BC$ . Wybierzmy prostą $p$ równoległą do $BC$ , przecinającą odcinki $AB,AC$ w punktach odpowiednio $D,E$ . Oznaczmy przez $l$ okrąg wpisany w trójkąt $ADE$ . Styczne do okręgu $k$ przechodzące przez punkty $D,E$ i nie zawierające punktu $A$ przecinają się w punkcie $P$ . Styczne do okręgu $l$ przechodzące przez punkty $B,C$ i nie zawierające punktu $A$ przecinają się w punkcie $Q$ . Dowieść, że prosta $PQ$ przechodzi przez pewien ustalony punkt, niezależny od wyboru prostej $p$ .

Rozwiązanie

Załóżmy, że prosta $BC$ jest styczna do $k$ w punkcie $T_k$ , a prosta $DE$ jest styczna do $l$ w punkcie $T_l$ . Wykażemy, że szukanym punktem jest $T_k$ .

Najpierw udowodnimy, że punkty $T_k$ , $T_l$ i $P$ są współliniowe. Oznaczmy przez $U$ i $V$ punkty wspólne okręgu $k$ ze stycznymi odpowiednio $EP$ i $DP$ , zaś przez $M$ i $N$ punkty przecięcia prostej $BC$ z prostymi odpowiednio $EP$ i $DP$ . Niech $T_1$ , $T_2$ będą punktami styczności półprostych $AB$ , $AC$ do okręgu $k$ .

Ze względu na $BC\|DE$ , trójkąty $DEP$ i $NMP$ są podobne i jednokładność $\mathcal H$ o środku $P$ i skali $q=MN/ED$ odwzorowuje odcinek $DE$ na $NM$ . Aby udowodnić współliniowość $T_k$ , $T_l$ i $P$ , wystarczy zatem sprawdzić, że

$ (1) \qquad \frac{MT_k}{NT_k}=\frac{ET_l}{DT_l}, $

gdyż wtedy $\mathcal H$ odwzorowuje $T_l$ na $T_k$ .

Oznaczmy przez $a$ , $b$ , $c$ długości boków trójkąta $DEP$ i niech $AD=e$ oraz $AE=d$ . Przypomnijmy ponadto znany fakt: W dowolnym trójkącie $XYZ$ odległości wierzchołka $X$ od punktów styczności $XY$ z okręgiem wpisanym i dopisanym wynoszą odpowiednio $(XY+XZ-YZ)/2$ i $(XY+YZ-XZ)/2$ . Stosując to twierdzenie do trójkąta $NMP$ i jego okręgu dopisanego $k$ , otrzymujemy

$ (2) \qquad \frac{MT_k}{NT_k}=\frac{(MN+NP-MP)/2}{(MN+MP-NP)/2}=\frac{qa+qc-qb}{qa+qb-qc}=\frac{a+c-b}{a+b-c}. $

Korzystając ponownie z wspomnianego twierdzenia, w przypadku okręgu $l$ wpisanego w trójkąt $DEA$ mamy

$ (3) \qquad \frac{ET_l}{DT_l}=\frac{(DE+AE-AD)/2}{(DE+AD-AE)/2}=\frac{a+d-e}{a+e-d}. $

Wiadomo, że jeżeli z pewnego punktu poprowadzimy styczne do okręgu, to odległości między wyjściowym punktem a otrzymanymi punktami styczności są takie same. Powtarzając wielokrotnie ten argument, wnioskujemy, że

$ e+c+PU=e+c+PV=e+DT_1=AT_1=AT_2=d+ET_2=d+b+PU, $

a stąd $e+c=d+b$ . Zatem $c-b=d-e$ i wstawiając tę zależność do (2) i (3) otrzymujemy

$ \frac{MT_k}{NT_k}=\frac{a+(c-b)}{a-(c-b)}=\frac{a+(d-e)}{a-(d-e)}=\frac{ET_l}{DT_l}, $

czyli zależność (1) jest prawdziwa. Zatem punkt $P$ leży na odcinku $T_lT_k$ .

Podobnie dowiedziemy, że punkty $T_k$ , $T_l$ i $Q$ są współliniowe. Niech $U'$ i $V'$ będą punktami styczności $CQ$ i $BQ$ do okręgu $l$ , zaś $M'$ i $N'$ punktami przecięcia $DE$ z $CQ$ i $BQ$ . Przez $T_1'$ i $T_2'$ oznaczamy punkty styczności $l$ i półprostych odpowiednio $AD$ i $AE$ . Niech ponadto $a'$ , $b'$ , $c'$ będą długościami boków trójkąta $BCQ$ oraz niech $AB=e'$ i $AC=d'$ .

Powtarzając rozumowanie z pierwszej części rozwiązania (tym razem mamy do czynienia z dwoma okręgami dopisanymi), otrzymujemy

$ \frac{M'T_l}{N'T_l}=\frac{a'+c'-b'}{a'+b'-c'},\qquad \frac{CT_k}{BT_k}=\frac{a'+e'-d'}{a'+d'-e'}. $

Porównując długości odpowiednich odcinków, mamy

$ e'-c'-QU'=e'-c'-QV'=e'-BT_1'=AT_1'=AT_2'=d'-CT_2'=d'-b'-QU', $

skąd $c'-b'=e'-d'$ oraz

$ \frac{M'T_l}{N'T_l}=\frac{CT_k}{BT_k}. $

Z podobieństwa trójkątów $BCQ$ i $N'M'Q$ wnioskujemy, że $Q$ leży na odcinku $T_lT_k$ .

Zatem prosta $PQ$ (oczywiście $P\neq Q$ ) pokrywa się z prostą $T_lT_k$ i przechodzi przez punkt $T_k$ , który nie zależy od wyboru prostej $p$ .

IX CPS - Zadanie 4

Zawody matematyczne:

IX CPS, 2009

Dany jest okrąg $k$ i jego cięciwa $AB$ , nie będąca średnicą. Niech $C$ będzie dowolnym punktem na dłuższym łuku $AB$ okręgu $k$ . Oznaczmy przez $K,L$ odbicia punktów $A,B$ względem prostych odpowiednio $BC,AC$ . Udowodnić, że odległość między środkami odcinków $AB$ i $KL$ nie zależy od wyboru punktu $C$ .

Rozwiązanie

Sposób I

Niech $\alpha$ , $\beta$ oraz $\gamma$ będą odpowiednio miarami kątów $\measuredangle CAB$ , $\measuredangle ABC$ oraz $\measuredangle BCA$ . Na mocy założenia zadania kąt $\measuredangle BCA$ jest zawsze ostry. Możemy założyć, że $\alpha<90^{\circ}$ , gdyż w drugim przypadku, $\beta<90^{\circ}$ , rozumowanie jest analogiczne. Niech $S$ , $M$ , $U$ , $V$ będą środkami odcinków odpowiednio $AB$ , $KL$ , $AL$ , $BK$ . Niech ponadto $H$ będzie punktem przecięcia prostych $AK$ i $BL$ .

Zauważmy, że czworokąt $USVM$ jest równoległobokiem ( $SU\|BL\|MV$ , $SV\|AK\|MU$ ) oraz

$ SV=AB\sin\beta,\quad MV=SU=AB\sin\alpha,\quad\measuredangle SVM=\measuredangle AHL=\measuredangle ACB=\gamma. $

Z twierdzenia sinusów zastosowanego do trójkąta $ABC$ wynika, że

$ \frac{AC}{SV}=\frac1{AB}\cdot\frac{AC}{\sin\beta}=\frac1{AB}\cdot\frac{BC}{\sin\alpha}=\frac{BC}{MV}, $

więc trójkąty $SVM$ i $ACB$ są podobne (cecha bok-kąt-bok). Ponownie korzystamy z twierdzenia sinusów i otrzymujemy

$ SM=AB\cdot\frac{SV}{AC}=\frac{AB^2\sin\beta}{AC}=\frac{AB^2\sin\gamma}{AB}=AB\sin\gamma=2r, $

gdzie $r$ jest promieniem okręgu $k$ , niezależnym od wyboru punktu $C$ .

Sposób II

Niech $S$ będzie środkiem odcinka $AB$ , $M$ - środkiem odcinka $KL$ , $P$ i $Q$ - spodkami wysokości odpowiednio z wierzchołków $A$ i $B$ trójkąta $ABC$ . Oczywiście $P$ i $Q$ są środkami odcinków $AK$ i $BL$ , więc

$ QS=\tfrac12LA=MP\qquad\text{i}\qquad QS\|LA\|MP, $

a zatem $SPMQ$ jest równoległobokiem (nawet w przypadku zdegenerowanego trójkąta $LAB$ lub $LAK$ ).

Kąty $APB$ i $AQB$ są proste, punkty $P$ i $Q$ leżą na okręgu o średnicy $AB$ , więc $SP=SQ=\frac{1}{2}AB$ . Z tego wynika, że równoległobok $SPMQ$ jest rombem i długość jego boków nie zależy od położenia punktu $C$ . Aby wykazać, że również długość jego przekątnej $SM$ jest niezależna od $C$ , wystarczy sprawdzić, że miara kąta wyznaczonego przez boki $SP$ i $SQ$ nie zmienia się podczas przesuwania $C$ po okręgu $k$ (wtedy wszystkie romby $SPMQ$ są przystające).

Jeśli kąt $\alpha$ w trójkącie $ABC$ jest ostry, punkt $Q$ leży na odcinku $AC$ i kąt $PSQ$ jest kątem środkowym koła o średnicy $AB$ , opartym na tym samym łuku co kąt wpisany $PAQ$ . Zatem

$ \measuredangle PSQ=2\cdot\measuredangle PAQ=2(90^\circ-\gamma)=180^\circ-2\gamma. $

Ten sam wzór otrzymujemy w przypadku, gdy $\alpha$ nie jest kątem ostrym, ponieważ wtedy $\beta$ jest ostry i możemy rozważać kąt wpisany $PBQ$ zamiast $PAQ$ :

$ \measuredangle PSQ=2\cdot\measuredangle PBQ=2(90^\circ-\gamma)=180^\circ-2\gamma. $

Wiadomo, że $\gamma$ nie zmienia się przy przesuwaniu $C$ po okręgu $k$ , ponieważ jest miarą kąta wpisanego, opartego na ustalonym łuku $AB$ , a zatem miara kąta $PSQ$ również pozostaje niezmienna. Wobec wcześniejszych uwag to kończy dowód.

IX CPS - Zadanie 5

Liczby całkowite dodatnie $a_1,a_2,\dots,a_n$ spełniają następujące warunki:

$1\leq a_1<a_2<\dots<a_n\leq50$ ;
dla dowolnych liczb całkowitych dodatnich $b_1,b_2,\dots,b_n$ istnieje taka liczba całkowita dodatnia $m$ oraz liczby całkowite dodatnie $c_1,c_2,\dots,c_n$ , że

$ mb_i=(c_i)^{a_i}\text{ dla }i=1,2,\dots,n. $

Wykazać, że $n\leq16$ oraz wyznaczyć liczbę różnych ciągów $(a_1,a_2,\dots,a_n)$ spełniających powyższe warunki dla $n=16$ .

Rozwiązanie

Zaczniemy od uzasadnienia, że liczby $a_1,\dots,a_n$ są parami względnie pierwsze. Załóżmy, że tak nie jest. Wtedy $\gcd(a_i,a_j)=d>1$ dla pewnych $i\neq j$ . Niech $a_i=u\cdot d$ i $a_j=v\cdot d$ . Na mocy (ii) dla $b_i=1$ i $b_j=2$ istnieją $m$ , $c_i$ i $c_j$ , spełniające warunek

$ m\cdot b_i=c_i^{a_i}\quad\text{i}\quad m\cdot b_j=c_j^{a_j}, \quad\text{lub równoważnie}\quad m=(c_i^u)^d\quad\text{i}\quad 2m=(c_j^v)^d. $

Zatem $2(c_i^u)^d=(c_j^v)^d$ , co jest niemożliwe, bo po rozłożeniu na czynniki pierwsze obu stron tego równania wykładnik 2 w wyrażeniu z lewej strony nie jest podzielny przez $d$ , zaś po prawej stronie 2 występuje z wykładnikiem podzielnym przez $d$ . Otrzymana sprzeczność dowodzi, że $a_1, \dots, a_n$ są względnie pierwsze.

Wykażemy teraz, że dla dowolnych $a_1, \dots, a_n$ , które są parami względnie pierwsze, warunek (ii) jest spełniony. Niech $b_1$ , \dots, $b_n$ będą dowolnymi dodatnimi liczbami całkowitymi, a $\{p_1,\dots,p_k\}$ będzie zbiorem wszystkich dzielników pierwszych liczby $b_1\cdot b_2\cdot\dots\cdot b_n$ . Szukamy liczby $m$ postaci

$ m=p_1^{\alpha_1}\cdot\dots\cdot p_k^{\alpha_k}. $

Dla $i=1,\dots,n$ oznaczmy przez $\beta_{i,j}$ wykładnik przy podstawie $p_j$ w rozkładzie na czynniki pierwsze liczby $b_i$ . Do tego by $m\cdot b_i$ była $a_i$ -tą potęga liczby całkowitej, wystarczy, by $\alpha_j+\beta_{i,j}$ była wielokrotnością $a_i$ , dla $j=1,\dots,k$ . Wystarczy zatem znaleźć $\alpha_j$ spełniające poniższe kongruencje:

$ \alpha_j\equiv-\beta_{1,j}\pmod{a_1},\quad \alpha_j\equiv-\beta_{2,j}\pmod{a_2}, $

$ \dots,\quad\alpha_j\equiv-\beta_{n,j}\pmod{a_n}. $

Istnienie takiego $\alpha_j$ wynika z chińskiego twierdzenia o resztach, ponieważ $a_1, \dots, a_n$ są względnie pierwsze.

Udowodniliśmy, że warunek (ii) jest jest spełniony wtedy i tylko wtedy, gdy liczby $a_1, \dots, a_n$ są parami względnie pierwsze. W zbiorze $\{1,2,\dots,50\}$ jest dokładnie 15 liczb pierwszych. Gdyby $n\geq17$ , wśród liczb $a_2,a_3,\dots,a_n$ znaleźlibyśmy przynajmniej dwie, które mają wspólny dzielnik pierwszy, gdyż $2\leq a_2<a_3<\dots<a_n\leq50$ . Jest to sprzeczne z faktem, że $a_1,\dots,a_n$ są względnie pierwsze, a stąd $n\leq16$ .

Dla $n=16$ , z powyższych rozważań wynika, że $a_1=1$ , zaś $a_2$ , $a_3, \dots, a_{16}$ muszą być potęgami różnych liczb pierwszych. Ze względu na to, że $a_{16}\leq50$ , dopuszczalne potęgi liczb pierwszych $p$ ( $p<50$ ), to:

$ \begin{array}{rl} p=2\colon&2,4,8,16,32,\\ p=3\colon&3,9,27,\\ p=5\colon&5,25,\\ p=7\colon&7,49,\\ p\geq11\colon&1. \end{array} $

Zatem liczba możliwych ciągów $a_1, \dots, a_{16}$ wynosi $5\cdot3\cdot2\cdot2=60$ .

IX CPS - Zadanie 6

Zawody matematyczne:

IX CPS, 2009

Dana jest liczba całkowita $n\geq 16$ . Rozważmy zbiór

$ G=\left\{(x,y)\colon x,y\in\{1,2,\dots,n\}\right\}, $

składający się z $n^2$ punktów płaszczyzny. Niech $A$ będzie dowolnym podzbiorem $G$ , zawierającym co najmniej $4n\sqrt{n}$ punktów. Udowodnić, że istnieje co najmniej $n^2$ czworokątów wypukłych, o wierzchołkach w zbiorze $A$ , takich że przekątne każdego z nich przechodzą przez jeden ustalony punkt płaszczyzny.

Rozwiązanie

Niech $|A|=m\geq4n\sqrt{n}$ i niech $\mathcal S$ będzie zbiorem wszystkich odcinków o obu końcach w zbiorze $A$ . Wtedy $|\mathcal S|=\binom m2$ i obie współrzędne środka dowolnego odcinka z $\mathcal S$ są naturalnymi wielokrotnościami $1/2$ . W kwadracie $\{(x,y)\colon 1\leq x\leq n, 1\leq y\leq n\}$ jest mniej niż $4n^2$ punktów o współrzędnych będących naturalnymi wielokrotnościami $1/2$ , zatem na mocy zasady szufladkowej istnieje punkt $X$ , który jest środkiem przynajmniej $\binom m2/(4n^2)$ odcinków ze zbioru $\mathcal S$ . Niech $\mathcal P$ będzie zbiorem wszystkich odcinków z $\mathcal S$ , których środkiem jest $X$ . Wtedy

$ \begin{split} |\mathcal P|&\geq\frac{\binom m2}{4n^2}=\frac{m(m-1)}{8n^2}\geq\frac{4n\sqrt{n}(4n\sqrt{n}-1)}{8n^2}=\\ &=\frac{16n^3-4n\sqrt{n}}{8n^2}=2n-\frac{1}{2\sqrt n}>2n-1, \end{split} $

czyli $|\mathcal P|\geq2n$ .

Podzielmy $\mathcal P$ na rozłączne rodziny odcinków zawartych w tej samej prostej. Załóżmy, że tych rodzin jest $k$ oraz $i$ -ta rodzina liczy $a_i$ odcinków, dla $i=1,\dots,k$ . Każdy odcinek z $a_i$ ma końce należące do $G$ i środek $X$ , więc $a_i\leq n/2$ . Ponadto każde dwa odcinki z $\mathcal P$ są przekątnymi równoległoboku wtedy i tylko wtedy, gdy nie leżą na tej samej linii. Z tego wynika, że liczba różnych równoległoboków o przekątnych ze zbioru $\mathcal P$ jest nie mniejsza niż

$ \begin{split} \sum_{i=1}^{k-1}\sum_{j=i+1}^k a_i a_j &= \frac12\left(\left(\sum_{i=1}^ka_i\right)^2-\sum_{i=1}^ka_i^2\right)\geq \\ \geq\frac12\left(\left(\sum_{i=1}^ka_i\right)^2-\sum_{i=1}^ka_i\cdot\frac n2\right) &= \frac12\left(|\mathcal P|^2-|\mathcal P|\cdot\frac n2\right)=\\ =\frac12|\mathcal P|\left(|\mathcal P|-\frac n2\right)&\geq n\left(2n-\frac n2\right)=\frac32n^2>n^2. \end{split} $

Zatem istnieje więcej niż $n^2$ czworokątów wypukłych (równoległoboków) spełniających warunki zadania.

Uwaga: Stosując nieco dokładniejsze oszacowania, można udowodnić tezę zadania wymagając dodatkowo, by współrzędne wspólnego punktu $X$ były liczbami naturalnymi.