XLVI OM - III etap

III etap XLVI Olimpiady Matematycznej

XLVI OM - III - Zadanie 1

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Wyznaczyć liczbę podzbiorów zbioru $\{1,2, \ldots , 2n\}$ , w których równanie $x + y = 2n+1$ nie ma rozwiązań.

Rozwiązanie

Zbiór $A$ , zawarty w zbiorze $\{1,2,\ldots,2n\}$ , będziemy nazywali dobrym, jeśli ma on wymaganą w zadaniu własność; to znaczy, gdy równanie $x + y = 2n + 1$ nie ma rozwiązania $x,y \in A$ .

Zbiór $\{1,2,\ldots,2n\}$ jest sumą następujących rozłącznych podzbiorów dwuelementowych (czyli par liczb):

$ P_1 = \{1,2n\},\ P_2 = \{2,2n-1\}, \ \ldots,\ P_n = \{n,n+1\}; $

symbol $P_j$ oznacza parę $\{j, 2n+1-j\}$ .

Podzbiór $A$ zbioru $\{1,2,\ldots,2n\}$ jest dobry wtedy i tylko wtedy, gdy nie zawiera żadnej pary $P_j$ , czyli - równoważnie - gdy dla każdego numeru $j \in \{1,2,\ldots,n\}$ część wspólna $P_j \cap A$ jest albo zbiorem pustym, albo zbiorem jednoelementowym $\{j\}$ , albo zbiorem jednoelementowym $\{2n+1-j\}$ . Dobry zbiór $A$ jest więc jednoznacznie wyznaczony przez wybór jednej z tych trzech opcji dla każdego $j \in \{1,2,\ldots,n\}$ . Stąd wniosek, że liczba dobrych zbiorów wynosi $3^n$ .

XLVI OM - III - Zadanie 2

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Przekątne pięciokąta wypukłego dzielą ten pięciokąt na pięciokąt i dziesięć trójkątów. Jaka jest maksymalna możliwa do uzyskania liczba trójkątów o równych polach?

Rozwiązanie

Oznaczmy rozważany pięciokąt przez $ABCDE$ , a pięciokąt utworzony przez punkty przecięcia przekątnych - przez $KLMNP$ tak, by następujące trójkąty były tymi, o których mowa w zadaniu:

$\Delta_0$ : trójkąt $LEM$ ; $\quad \Delta_1$ : trójkąt $EMA$ ;
$\Delta_2$ : trójkąt $MAN$ ; $\quad \Delta_3$ : trójkąt $ANB$ ;
$\Delta_4$ : trójkąt $NBP$ ; $\quad \Delta_5$ : trójkąt $BPC$ ;
$\Delta_6$ : trójkąt $PCK$ ; $\quad \Delta_7$ : trójkąt $CKD$ ;
$\Delta_8$ : trójkąt $KDL$ ; $\quad \Delta_9$ : trójkąt $DLE$

(rysunek 12). Rozpoczniemy od wykazania implikacji:

$ (1) \qquad \begin{array}{l} \textrm{jeśli numer $i$ jest liczbą nieparzystą},\\ \textrm{to pola trójkątów $\Delta_{i-1}$, $\Delta_i$, $\Delta_{i+1}$ nie są wszystkie równe}; \end{array} $

przyjmujemy, że numeracja trójkątów jest cykliczna (to znaczy, przyjmujemy: $\Delta_{-1} = \Delta_9$ ; $\Delta_{10} = \Delta_0$ ).

Przypuśćmy, że na przykład trójkąty $\Delta_4$ , $\Delta_5$ , $\Delta_6$ mają równe pola. Z równości pol trójkątów $NBP$ i $BPC$ wynika, że odcinek $BP$ jest środkową w trójkącie $BCN$ ; z równości pól trójkątów $BPC$ i $PCK$ wynika, że odcinek $CP$ jest środkową w trójkącie $BCK$ . Punkt $P$ byłby zatem wspólnym środkiem przekątnych $BK$ i $CN$ czworokąta $BCKN$ , który wobec tego powinien być równoległobokiem - ale przecież proste $BN$ i $CK$ przecinają się w punkcie $E$ . Sprzeczność; implikacja (1) jest wykazana.

Przechodzimy do właściwego rozwiązania. Przykład pięciokąta foremnego pokazuje, że można uzyskać pięć trójkątów $\Delta_i$ o równych polach. Udowodnimy, że nie można uzyskać siedmiu takich trójkątów.

Przypuśćmy więc, że istnieje siedmioelementowy zbiór $Z$ , zawarty w zbiorze $\{0,1,\ldots,9\}$ , taki, że trójkąty $\Delta_i$ o numerach $i \in Z$ mają równe pola. Niech $k$ , $l$ , $m$ będą trzema liczbami ze zbioru $\{0,1,\ldots,9\}$ , nie należącymi do $Z$ . Weźmy pod uwagę wszystkie trójki kolejnych indeksów:

$ T_i = \{i-1,i,i+1\} \quad \textrm{dla} \quad i = 0,1,\ldots,9 $

(gdzie, jak poprzednio, dodawanie $i \pm 1$ należy rozumieć modulo $10$ ). Każda z liczb ze zbioru $\{0,1,\ldots,9\}$ należy do dokładnie trzech trójek $T_i$ . Dotyczy to, w szczególności, każdej z liczb $k$ , $l$ , $m$ . Łącznie więc trójelementowy zbiór $\{k,l,m\}$ ma niepuste przecięcie z co najwyżej dziewięcioma trójkami $T_i$ . Zostaje co najmniej jedna trójka $T_j$ nie zawierająca żadnej z liczb $k$ , $l$ , $m$ , a więc zawarta w zbiorze $Z$ . Numer $j$ musi być liczbą parzystą, w myśl spostrzeżenia (1).

Nie tracąc ogólności przyjmijmy, że $j = 2$ . To znaczy, że liczby $1$ , $2$ , $3$ należą do zbioru $Z$ . Wobec tego liczby $0$ i $4$ nie mogą doń należeć (bowiem - znów na mocy uwagi (1) - wykluczone są trójki $\{0,1,2\}$ oraz $\{2,3,4\}$ ); zatem jedna z liczb $k$ , $l$ , $m$ równa się $0$ , a inna równa się $4$ . Trzecia z tych liczb musi wchodzić w skład trójki $\{6,7,8\}$ (która w przeciwnym razie byłaby zawarta w zbiorze $Z$ , wbrew implikacji (1)). Role numerów $6$ i $8$ są w tym kontekście symetryczne. Mamy więc do rozpatrzenia dwie istotnie różne sytuacje:

$ \{k,l,m\} = \{0,4,7\}\quad \textrm{oraz} \quad \{k,l,m\} = \{0,4,6\}; $

zbiór $Z$ , odpowiednio, ma jedną z następujących postaci:

$ Z= \{1,2,3,5,6,8,9\},\quad Z = \{1,2,3,5,7,8,9\}. $

Niech $S_i$ będzie polem trójkąta $\Delta_i$ ; (dla $i = 0,1,\ldots,9$ ). Wykażemy, że zachodzą implikacje:

$ (2) \qquad (S_1 = S_2 = S_3,\quad S_5 = S_6,\quad S_8 = S_9) \Longrightarrow (S_3<S_5); $

$ (3) \qquad (S_1 = S_2 = S_3,\quad S_7 = S_8 = S_9) \Longrightarrow (S_2>S_5). $

Będzie to dowód, że żaden z wypisanych powyżej siedmioelementowych zbiorów $Z$ nie może być zbiorem numerów trójkątów o równych polach. W myśl wcześniejszych stwierdzeń, będzie to jednocześnie uzasadnienie wniosku, że wśród dziesięciu trójkątów $\Delta_i$ nigdy nie ma siedmiu trójkątów o jednakowych polach.

Dowód implikacji (2). Z danych w przesłance równości pól:

$ \textrm{pole}(MAN) = \textrm{pole}(ANB), \quad \textrm{pole}(BPC) = \textrm{pole}(PCK) $

oraz

$ \textrm{pole}(EMA) = \textrm{pole}(MAN), \quad \textrm{pole}(KDL) = \textrm{pole}(DLE) $

wynika (odpowiednio), że punkty $N$ i $P$ są środkami odcinków $BM$ i $BK$ , a punkty $M$ i $L$ są środkami odcinków $EN$ i $EK$ (rysunek 13).

Tak więc odcinek $NP$ łączy środki dwóch boków trójkąta $BMK$ , odcinek $ML$ łączy środki dwóch boków trójkąta $ENK$ , i wobec tego

$ |NP| = \frac{1}{2} \cdot |MK|,\quad NP||MK \quad \textrm{- czyli} \quad AN||MK $

- oraz

$ |ML| = \frac{1}{2} \cdot |NK|, \quad ML||NK \quad \textrm{- czyli} \quad AM||NK. $

Uzyskane związki równoległości pokazują, że czworokąt $AMKN$ jest równoległobokiem; stąd $|MK|= |AN|$ . Prosta $MK$ jest równoległa do $NC$ , więc trójkąty $ENC$ i $EMK$ są jednokładne w skali $|EN|\colon |EM| = 2$ . W takim razie $|NC| = 2 \cdot |MK|$ , i w konsekwencji

$ |PC|= |NC|-|NP| = 2\cdot|MK|-\frac{1}{2} \cdot |MK| = \frac{3}{2} \cdot |MK| = \frac{3}{2} \cdot |AN|. $

Leżące na jednej prostej odcinki $PC$ i $AN$ są podstawami trójkątów $ANB$ i $BPC$ o wspólnym wierzchołku $B$ . Stosunek długości tych podstaw jest więc jednocześnie stosunkiem pól trójkątów: pole( $BPC$ ): pole( $ANB$ ) = $3 \colon 2$ , czyli $S_5 \colon S_3 = 3 \colon 2$ . Konkluzja implikacji (2) jest tym samym udowodniona.

Dowód implikacji (3). Dane w przesłance równości pól trójkątów:

$ (4) \qquad \quad \textrm{pole}(AEM) = \textrm{pole}(AMN) = \textrm{pole}(ANB) $

oraz

$ (5) \qquad \quad \textrm{pole}(DEL) = \textrm{pole}(DLK) = \textrm{pole}(DKC) $

pokazują, że punkty $M$ i $N$ dzielą odcinek $EB$ na trzy równe części, i podobnie punkty $L$ i $K$ dzielą odcinek $EC$ na trzy równe części. Wobec tego prosta $BC$ jest równoległa do $ML$ (czyli do $AM$ ). Skoro zaś $N$ jest środkiem odcinka $BM$ , zatem trójkąty $AMN$ i $CBN$ są jednokładne w skali $-1$ (rysunek 14). Stąd wniosek, że pole( $AMN$ ) = pole( $CBN$ ) $>$ pole( $CBP$ ), czyli $S_2 > S_5$ . To kończy dowód implikacji (3), i tym samym także dowód ogólnej tezy: nie można mieć siedmiu trójkątów $\Delta_i$ o równych polach.

Przeprowadzone w tym ostatnim przypadku rozumowanie (dowód (3)) daje jednocześnie wskazówkę, jak uzyskać sześć trójkątów $\Delta_i$ mających jednakowe pola. Bierzemy dowolny trójkąt równoramienny $BCE$ , w którym $|EB| = |EC|$ . Na bokach $EB$ oraz $EC$ znajdujemy punkty $M$ i $N$ oraz $L$ i $K$ , dzielące te boki na trzy równe części:

$ |EM| = |MN| = |NB|,\quad |EL| = |LK| = |KC|. $

Punkty przecięcia prostej $ML$ z prostymi $CN$ oraz $BK$ oznaczmy odpowiednio przez $A$ i $D$ (rysunek 14 może nadal służyć jako ilustracja; trzeba tylko w wyobraźni przesunąć punkt $E$ do położenia na symetralnej boku $BC$ , i odpowiednio przemieścić pozostałe punkty). Zachodzą wówczas równości (4) oraz (5); a dzięki założeniu, że trójkąt $BCE$ jest równoramienny (i wynikającej stąd symetrii całej konfiguracji) osiągamy to, że wszystkie pola występujące w związkach (4) oraz (5) są równe.

Wniosek: sześć spośród trójkątów $\Delta_i$ może mieć równe pola, i liczby tej nie można już zwiększyć.

XLVI OM - III - Zadanie 3

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Dana jest liczba pierwsza $p \geq 3$ . Określamy ciąg $(a_n)$ wzorami

$ \begin{split} a_n = n & \text{ dla } n=0,1,2,\ldots,p-1, \\ a_n = a_{n-1} + a_{n-p} & \text{ dla } n\geq p. \end{split} $

Wyznaczyć resztę z dzielenia liczby $a_{p^3}$ przez $p$ .

Rozwiązanie

Podany wzór rekurencyjny

$ (1) \qquad \quad a_n = a_{n-1} + a_{n-p} \quad \textrm{dla} \quad n \geq p $

możemy zastosować do każdego ze składników jego prawej strony (pod warunkiem, że numer $n - p$ jest nie mniejszy od $p$ , czyli że $n \geq 2p$ ); dostajemy zależność

$ a_n = (a_{n-2} + a_{n-1-p}) + (a_{n-p-1} + a_{n-2p}) = a_{n-2} + 2a_{n-1-p} + a_{n-2p}. $

Stosując ponownie wzór (1) do każdego ze składników ostatniej sumy otrzymujemy równość

$ \begin{split} a_n &= (a_{n-3}+ a_{n-2-p}) + 2(a_{n-p-2}+ a_{n-1-2p}) + (a_{n-2p-1} +a_{n-3p}) = \\ & = a_{n-3} + 3a_{n-2-p} + 3a_{n-1-2p} + a_{n-3p} \end{split} $

(jeśli tylko $n \geq 3p$ ). Po $k$ -krotnym zastosowaniu analogicznego przekształcenia uzyskujemy związek

$ \begin{split} (2) \qquad \quad a_n & = a_{n-k} + {{k}\choose{1}} a_{n-k+1-p} + {{k}\choose{2}} a_{n-k+2-2p}+\ldots+ a_{n-kp}=\\ & = \sum_{i=0}^k {{k}\choose{i}} a_{n-k+i-ip}, \end{split} $

sensowny i słuszny pod warunkiem że $n \geq kp$ .

(Wyprowadzenie wzoru (2) ma charakter indukcyjny; proponujemy Czytelnikowi, jako proste ćwiczenie, przeprowadzenie szczególowego uzasadnienia, przez indukcję względem $k = 1,2,\ldots,[n/p]$ , z wielokrotnym wykorzystaniem wzoru (1).)

Jeśli teraz $n \geq p^2$ , to możemy w równości (2) podstawić $k = p$ , otrzymując

$ (3) \qquad \quad a_n = \sum_{i=0}^p {{p}\choose{i}} a_{n+i -(i+1)p}. $

Dla $i = 1,2,\ldots,p-1$ współczynniki dwumianowe ${{p}\choose{i}}$ są liczbami podzielnymi przez $p$ (patrz: Uwaga). Jeśli więc z sumy napisanej po prawej stronie równości (3) odrzucimy wszystkie składniki z wyjątkiem dwóch skrajnych (odpowiadających wartościom wskaźnika $i = 0$ oraz $i = p$ ), to otrzymamy liczbę przystającą do $a_n$ modulo $p$ :

$ (4) \qquad \quad a_n \equiv a_{n-p} +a_{n-p^2} \pmod p $

(dla $n \geq p^2$ ). Przyrównując (modulo $p$ ) prawe strony związków (1) i (4) stwierdzamy, że $a_{n-1}+a_{n-p} \equiv a_{n-p} + a_{n-p^2}$ , czyli

$ a_{n-1} \equiv a_{n-p^2} \pmod p. $

Oznaczmy przez $r_j$ resztę z dzielenia liczby $a_j$ przez $p$ (dla $j = 0,1,2,\ldots$ ). Uzyskaną zależność przepisujemy w postaci

$ r_{n-1} = r_{n-p^2} \quad \textrm{dla} \quad n \geq p^2. $

To znaczy, że ciąg ( $r_j$ ) jest okresowy, z okresem $p^2-1$ ; zatem

$ r_n = r_{n-k(p^2-1)} \quad \textrm{dla} \quad k = 1,2,\ldots,[n/(p^2-1)]. $

Podstawiamy $n = p^3$ , $k = p$ , i otrzymujemy wynik:

$ r_{p^3}= r_{p^3-p(p^2-1)} = r_p. $

Pozostaje zauważyć, że (w myśl wzoru (1))

$ a_p = a_{p-1} +a_0 = (p-1) + 0 = p-1 $

i wobec tego $r_{p^3} = r_p = p-1$ . Tak więc reszta z dzielenia liczby $a_{p^3}$ przez $p$ równa się $p-1$ .

Uwaga. Fakt, na który powołaliśmy się w rozwiązaniu:

liczba pierwsza $p$ jest dzielnikiem liczb ${{p}\choose{1}}$ , ${{p}\choose{2}}$ , $\ldots$ , ${{p}\choose{p-1}}$

jest dobrze znany (oraz banalnie prosty: w równości ${{p}\choose{i}} \cdot (i!) \cdot ((p-i)!) = p!$ czynniki $i!$ oraz $(p-i)!$ są dla $i \in \{1,2,\ldots,p-1\}$ niepodzielne przez $p$ , więc czynnik ${{p}\choose{i}}$ musi dzielić się przez $p$ ).

XLVI OM - III - Zadanie 4

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Dla danej liczby naturalnej $n \geq 1$ wyznaczyć najmniejszą wartość wyrażenia

$ x_1 + \frac{x_2^2}{2} + \frac{x_3^3}{3} + \ldots + \frac{x_n^n}{n} $

gdzie $x_1, x_2, \ldots , x_n$ są liczbami dodatnimi spełniającymi warunek

$ \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{x_n} = n. $

Rozwiązanie

Kluczem do rozwiązania jest nierówność

$ (1) \qquad \quad \frac{x^k}{k} + \frac{1}{x} \geq 1 + \frac{1}{k} \quad \textrm{dla} \quad x>0,\ k = 1,2,3,\ldots. $

Oto jej dowód: różnica między wyrażeniem po lewej stronie (1) i wyrażeniem po prawej stronie (1), pomnożona przez dodatni czynnik $kx$ , jest równa

$ (x^{k+1}+k)-(kx + x) = x(x^k-1) + k(1-x) = x(x-1) \sum_{i=0}^{k-1} x^i + k(1-x) = $

$ = (x-1) \left( \sum_{j=1}^k x^j-k \right) = (x-1) \sum_{j=1}^k (x^j-1) = \sum_{j=1}^k (x-1)(x^j-1). $

Ta suma jest nieujemna, bo wszystkie jej składniki są liczbami nieujemnymi.

Podstawiamy w (1) $x = x_k$ dla $k = 1,\ldots,n$ (gdzie $x_1,\ldots,x_n$ są danymi w zadaniu liczbami) i dodajemy uzyskane nierówności stronami:

$ \sum_{k=1}^n \frac{x_k^k}{k} + \sum_{k=1}^n \frac{1}{x_k} \geq \sum_{k=1}^n \left( 1 + \frac{1}{k} \right) = n + \sum_{k=1}^n \frac{1}{k}. $

Druga suma po lewej stronie ma wartość $n$ , zgodnie z warunkiem danym w założeniach. A zatem

$ \sum_{k=1}^n \frac{x_k^k}{k} \geq \sum_{k=1}^n \frac{1}{k}. $

Gdy $x_1 = \ldots = x_n = 1$ , nierówność ta staje się równością. Tak więc minimalna wartość badanego wyrażenia wynosi $1 + \frac{1}{2} + \frac{1}{3} +\ldots + \frac{1}{n}$ .

Uwaga 1. Wyjściową nierówność (1) można uzasadnić wieloma sposobami. Na przykład tak: średnia arytmetyczna układu $k+1$ liczb, z których jedna jest równa $x^k$ , a pozostałe są równe $1/x$ , jest nie mniejsza niż średnia geometryczna tych liczb:

$ \frac{1}{1+k} \left( x^k + \underbrace{\frac{1}{x} + \ldots + \frac{1}{x}}_k \right) \geq \left( x^k \cdot \underbrace{\frac{1}{x} \cdot \ldots \cdot \frac{1}{x}}_k \right)^{1/(k+1)}=1; $

stąd $x^k + \dfrac{k}{x} \geq k+1$ , co jest równoważnym zapisem nierówności (1).

Można także w znanej nierówności Bernoulli'ego

$ (1 + a)^k \geq 1 + ka, $

zachodzącej dla wszystkich liczb $a \geq -1$ (oraz dla $k = 1,2,3,\ldots$ ), podstawić $a = x-1$ , otrzymując: $x^k \geq 1 + k(x - 1)$ . Stąd

$ \frac{x^k}{k} + \frac{1}{x} \geq \frac{1+k(x-1)}{k} + \frac{1}{x} = x+\frac{1}{x} + \frac{1}{k} -1 = 1+ \left( \sqrt{x} - \frac{1}{\sqrt{x}}\right)^2 + \frac{1}{k} \geq 1+\frac{1}{k}. $

Można wreszcie potraktować lewą stronę (1) jako funkcję zmiennej $x$ przebiegającej przedział $(0;\ \infty)$ i przekonać się, że jej pochodna jest ujemna w przedziale $(0;\ 1)$ oraz dodatnia w $(1;\ \infty)$ , wobec czego dla $x = 1$ osiągana jest wartość minimalna, równa $1 + (1/k)$ .

XLVI OM - III - Zadanie 5

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Niech $n$ i $k$ będą liczbami naturalnymi. Z urny, w której znajduje się 11 kartek ponumerowanych liczbami od 1 do $n$ , losujemy kartki kolejno po jednej, bez zwracania. Gdy pojawi się kartka o numerze podzielnym przez $k$ , przerywamy losowanie. Dla ustalonego $n$ wyznaczyć te liczby $k \leq n$ , dla których wartość oczekiwana liczby wylosowanych kartek jest równa dokładnie $k$ .

Rozwiązanie

Ustalmy liczbę naturalną $k \in \{1,2,\ldots,n\}$ . Weźmy pod uwagę następujące zdarzenia:

$ \begin{array}{cl} \mathcal{A}_j: & \textrm{liczba podzielna przez } k\ \textrm{pojawia się po raz pierwszy} \\ & \textrm{w } j\ \textrm{-tym losowaniu}\ (j=1,2,\ldots,n);\\ \mathcal{B}_j: & \textrm{liczba podzielna przez } k\ \textrm{nie pojawia się} \\ & \textrm{w żadnym spośród pierwszych} j\ \textrm{losowań}\ (j=0,1,2,\ldots,n). \end{array} $

Oznaczmy prawdopodobieństwa tych zdarzeń: $p_j = P(\mathcal{A}_j)$ , $q_j=P(\mathcal{B}_j$ ). Oczywiście $\mathcal{B}_0$ jest zdarzeniem pewnym. Zatem $q_0=1$ .

Zajście zdarzenia $\mathcal{A}_j$ jest równoważne temu, że wylosowano $j$ kartek, po czym losowanie przerwano - czyli temu, że rozważana w zadaniu zmienna losowa $X$ (liczba wylosowanych kartek) przyjmuje wartość $j$ . Tak więc

$ p_j = P(X=j)\quad \textrm{dla}\quad i = 1,2,\ldots,n. $

Zajście zdarzenia $\mathcal{A}_j$ jest jednocześnie równoważne temu, że liczba podzielna przez $k$ nie pojawiła się w pierwszych $j-1$ losowaniach, natomiast pojawiła się w pierwszych $j$ losowaniach - czyli że zaszło zdarzenie $\mathcal{B}_{j-1}$ , ale nie zaszło zdarzenie $\mathcal{B}_j$ . Inaczej mówiąc, zdarzenie $\mathcal{A}_j$ jest równe różnicy zdarzeń $\mathcal{B}_{j-1}$ i $\mathcal{B}_j$ (traktowanych jako podzbiory odpowiedniej przestrzeni probabilistycznej). Wobec tego

$ p_j = P(\mathcal{B}_{j-1} \setminus \mathcal{B}_j) = q_{j-1}-q_j \quad \textrm{dla}\quad j = 1,2,\ldots,n $

(korzystamy z tego, że $\mathcal{B}_j \subset \mathcal{B}_{j-1}$ ).

Wartość oczekiwana zmiennej losowej $X$ równa się

$ \begin{split} E(X) & = \sum_{j=1}^n j \cdot P(X=j) = \sum_{j=1}^n j \cdot p_j = \sum_{j=1}^n j(q_{j-1} - q_j)=\\ & = (q_0-q_1) + 2(q_1 -q_2) + 3(q_2 -q_3) + \ldots + n(q_{n-1} -q_n) = \\ & = q_0 + q_1 + q_2 + \ldots + q_{n-1} -nq_n. \end{split} $

W zbiorze $\{1,2,\ldots,n\}$ jest $m$ liczb podzielnych przez $k$ oraz jest $l$ liczb niepodzielnych przez $k$ , przy czym

$ m= \left[ \frac{n}{k} \right] \geq 1, \quad l = n-m \leq n-1 $

(symbol $[t]$ oznacza, jak zwykle, największą liczbę całkowitą, nie przekraczają $t$ ). Jeżeli $j > l$ , to w którymś z pierwszych $j$ losowań musiała pojawić się liczba podzielna przez $k$ , co oznacza, że $\mathcal{B}_j$ jest zdarzeniem niemożliwym. Zatem $q_j = 0$ dla $j > l$ , i w takim razie

$ (1) \qquad \quad E(X) = q_0+q_1 +q_2 + \ldots + q_l. $

Z warunków zadania wynika, że dla $j \leq l$ prawdopodobieństwa $q_j$ wyrażają się wzorem

$ (2) \qquad \quad q_j=P(\mathcal{B}_j) = \frac{l}{n} \cdot \frac{l-1}{n-1} \cdot \ldots \cdot \frac{l-j+1}{n-j+1} \quad (j\ \textrm{czynników}). $

Istotnie: w pierwszym losowaniu wyciągamy liczbę niepodzielną przez $k$ z prawdopodobieństwem $l/n$ ; zostaje w urnie $n-1$ kartek, w tym $l-1$ kartek z liczbami niepodzielnymi przez $k$ ; w drugim losowaniu wyciągamy liczbę niepodzielną przez $k$ z prawdopodobieństwem $(l- 1)/(n- 1)$ ; i tak dalej. Wyciągnięcie w $j$ kolejnych losowaniach kartek z liczbami niepodzielnymi przez $k$ odbywa się z prawdopodobieństwem równym iloczynowi napisanemu po prawej stronie wzoru (2).

Przekształcamy ten iloczyn, jak następuje:

$ q_j = \frac{l!}{(l-j)!} \cdot \frac{(n-j)!}{n!} = \frac{l!(n-l)!}{n!} \cdot \frac{(n-j)!}{(l-j)!(n-l)!}= $

$ ={{n}\choose{l}}^{-1} {{n-j}\choose{n-l}} = {{n}\choose{m}}^{-1} {{n-j}\choose{m}} $

(bo $l + m = n$ ). Po podstawieniu tych wyrażeń równość (1) przybiera postać

$ E(X) = {{n}\choose{m}}^{-1} \sum_{j=0}^{n-m} {{n-j}\choose{m}} = {{n}\choose{m}}^{-1} \sum_{s=m}^n {{s}\choose{m}} $

(zastosowaliśmy zmianę wskaźnika sumowania: $s = n-j$ ). Ostatnia suma daje się zwinąć w znany sposób:

$ \sum_{s=m}^n {{s}\choose{m}} = {{n+1}\choose{m+1}} $

(por. rozwiązanie zadania 11 z zawodów pierwszego stopnia tej olimpiady: wzór (2) oraz Uwaga na stronie 51). Stąd

$ E(X) = {{n}\choose{m}}^{-1} {{n+1}\choose{m+1}} = \frac{m!(n-m)!}{n!} \cdot \frac{(n+1)!}{(m+1)!(n-m)!} = \frac{n+1}{m+1}. $

W zadaniu chodzi o ustalenie warunków na to, by wartość $E(X)$ była równa dokładnie $k$ - czyli na to, by zachodziła równość

$ (3) \qquad \quad \frac{n+1}{m+1}=k. $

Jeśli związek (3) zachodzi, to oczywiście $k$ jest dzielnikiem liczby $n + 1$ . Na odwrót, jeśli $n+1$ dzieli się przez $k$ , wówczas z nierówności

$ \frac{n + 1}{k} - 1 \leq \frac{n}{k} < \frac{n+1}{k} $

(której skrajne człony są liczbami całkowitymi) wnosimy, że

$ m= \left[ \frac{n}{k} \right] = \frac{n+1}{k}-1, $

czyli zachodzi równość (3).

Mamy więc odpowiedź: szukanymi wartościami $k$ są wszystkie dzielniki liczby $n + 1$ należące do zbioru $\{1,2,\ldots,n\}$ .

XLVI OM - III - Zadanie 6

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Dane są trzy niewspółpłaszczyznowe półproste $k$ , $l$ , $m$ o wspólnym początku $P$ oraz punkt $A$ różny od $P$ należący do $k$ . Wykazać, że istnieje dokładnie jedna para punktów $B$ , $C$ , należących odpowiednio do $l$ i $m$ , taka, że

$ |PA| + |AB| = |PC| + |CB| \quad \text{oraz} \quad |PB| + |BC| = |PA| + |AC|. $

Rozwiązanie

Rozpoczniemy od analizy postulowanych warunków. Załóżmy, że punkty $B \in l$ , $C \in m$ spełniają te warunki:

$ (1) \qquad \quad |PA| + |AB| = |PC| + |CB|\quad \textrm{oraz}\quad |PB| + |BC| = |PA| + |AC|. $

W powstały trójkąt $ABC$ wpisujemy okrąg. Punkty styczności tego okręgu z bokami $BC$ , $CA$ , $AB$ oznaczmy odpowiednio przez $Q$ , $R$ , $S$ (rysunek 15). Zachodzą więc równości

$ (2) \qquad \quad |BS| = |BQ|,\quad |CQ| = |CR|,\quad |AR| = |AS|. $

Odejmujemy stronami pierwszą równość (2) od pierwszej równości (1): otrzymujemy związek $|PA| + |AB|-|BS| = |PC| + |CB|-|BQ|$ , czyli

$ (3) \qquad \quad |PA| +|AS| = |PC| + |CQ|. $

Następnie odejmujemy stronami drugą równość (2) od drugiej równości (1): dostajemy związek $|PB| + |BC|-|CQ| = |PA| + |AC|-|CR|$ , czyli

$ (4) \qquad \quad |PB| + |BQ| = |PA| + |AR|. $

Trzecia równość (2) pokazuje, że lewa strona (3) równa się prawej stronie (4). Oznaczmy tę wspólną wartość przez $t$ . Tak więc

$ (5) \qquad |PA| + |AR| = |PA| + |AS| = t, $

i wobec zależności (2) i (4) oraz (2) i (3):

$ (6) \qquad |PB| + |BS| = |PB| + |BQ| = t, $

$ (7) \qquad |PC| + |CR| = |PC| + |CQ| = t. $

Na półprostych $k$ , $l$ , $m$ odkładamy odcinki $PK$ , $PL$ , $PM$ o jednakowej długości $t$ : $|PK| = |PL| = |PM| = t$ . Liczba $t$ jest większa od każdej z odległości $|PA|$ , $|PB|$ , $|PC|$ , więc punkty $A$ , $B$ , $C$ leżą odpowiednio na odcinkach $PK$ , $PL$ , $PM$ . Wobec tego

$ (8) \qquad \begin{split} t=|PK| = |PA| & + |AK|,\quad t=|PL| = |PB| + |BL|, \\ & t=|PM| = |PC| + |CM|. \end{split} $

Porównując te związki z uzyskanymi wcześniej związkami (5), (6), (7) dochodzimy do równości

$ (9) \qquad \begin{split} |AK| = |AR| = & |AS|,\quad |BL| = |BQ| = |BS|,\\ & |CM| = |CQ| = |CR|. \end{split} $

Weźmy pod uwagę okrąg $\omega_1$ dopisany do trójkąta $PBC$ przy boku $BC$ ; punkty jego styczności z bokiem $BC$ oraz z przedłużeniami boków $PB$ i $PC$ oznaczmy odpowiednio przez $Q'$ , $L'$ , $M'$ . Oczywiście $|PL'| = |PM'|$ . Jednocześnie

$ |PL'| = |PB| + |BL'| = |PB| + |BQ'|, $

$ |PM'| = |PC| + |CM'| = |PC| + |CQ'|, $

skąd (wobec (6) i (7))

$ \begin{split} |PL'| + |PM'| & = |PB| + |PC| + |BQ'| + |CQ'| = |PB| + |PC| + |BC| =\\ & = |PB| + |PC| + |BQ| + |CQ| = 2t, \end{split} $

czyli $|PL'| = |PM'| = t$ . To znaczy, że punkt $L'$ pokrywa się z $L$ , a punkt $M'$ pokrywa się z $M$ . Ponadto $|BQ'| = |BL'| = |BL| = |BQ|$ , więc także punkt $Q'$ pokrywa się z $Q$ . Punkty $Q$ , $L$ , $M$ są zatem punktami styczności okręgu $\omega_1$ z prostymi $BC$ , $PB$ , $PC$ .

Analogicznie stwierdzamy, że punkty $R$ , $M$ , $K$ są punktami styczności okręgu $\omega_2$ , dopisanego do trójkąta $PCA$ , z bokiem $CA$ i z przedłużeniami boków $PC$ i $PA$ ; podobnie, punkty $S$ , $K$ , $L$ są punktami styczności okręgu $\omega_3$ , dopisanego do trójkąta $PAB$ , z bokiem $AB$ i z przedłużeniami boków $PA$ i $PB$ . Okręgi $\omega_1$ , $\omega_2$ , $\omega_3$ są więc styczne do płaszczyzny $ABC$ .

Przeprowadzona analiza daje wskazówkę do dowodu zarówno istnienia poszukiwanej pary punktów $B$ , $C$ , jak również jej jedyności.

Odłóżmy na półprostych $k$ , $l$ , $m$ odcinki $PK_0$ , $PL_0$ , $PM_0$ mające jednakową (dowolną) długość $s: |PK_0| = |PL_0| =|PM_0| = s$ . Weźmy pod uwagę trzy okręgi:

$\sigma_1$ - okrąg styczny do półprostych $l$ i $m$ w punktach $L_0$ i $M_0$ ,
$\sigma_2$ - okrąg styczny do półprostych $m$ i $k$ w punktach $M_0$ i $K_0$ ,
$\sigma_3$ - okrąg styczny do półprostych $k$ i $l$ w punktach $K_0$ i $L_0$ .

Istnieje wówczas dokładnie jedna płaszczyzna $\pi$ , styczna do tych trzech okręgów i taka, że punkty $K_0$ , $L_0$ , $M_0$ leżą po przeciwnej jej stronie niż punkt $P$ . Ten fakt, intuicyjnie jasny, można uzasadnić w następujący sposób.

Rozważamy ruchomy punkt $X$ , przebiegający odcinek $PK_0$ . Z punktu $X$ prowadzimy proste styczne do okręgów $\sigma_3$ i $\sigma_2$ , przecinające odcinki $PL_0$ i $PM_0$ odpowiednio w punktach $Y$ i $Z$ .

Gdy punkt $X$ znajduje się blisko punktu $P$ , punkty $Y$ i $Z$ leżą blisko punktów $L_0$ i $M_0$ ; odcinek $YZ$ przecina wówczas okrąg $\sigma_1$ (w dwóch punktach).

Gdy $X$ znajduje się blisko punktu $K_0$ , punkty $Y$ i $Z$ leżą blisko punktu $P$ ; odcinek $YZ$ jest wówczas rozłączny z okręgiem $\sigma_1$ .

Gdy $X$ przebiega odcinek $PK_0$ , oddalając się od jego końca $P$ , punkty $Y$ i $Z$ przebiegają odcinki $L_0P$ i $M_0P$ , zbliżając się do $P$ .

Istnieje zatem dokładnie jedno położenie punktu $X$ , wyznaczające punkty $Y$ i $Z$ tak, że odcinek $YZ$ jest styczny do okręgu $\sigma_1$ . Płaszczyzna $XYZ$ jest wówczas styczna do wszystkich trzech okręgów $\sigma_1$ , $\sigma_2$ , $\sigma_3$ ; jest to płaszczyzna $\pi$ , o którą nam chodziło. Wyznaczające tę płaszczyznę położenia punktów $X$ , $Y$ , $Z$ nazwijmy odpowiednio: $A_0$ , $B_0$ , $C_0$ .

Jeżeli szukane punkty $B$ i $C$ istnieją, to okręgi $\omega_1$ , $\omega_2$ , $\omega_3$ , określone w przeprowadzonej wcześniej analizie zadania, są obrazami okręgów $\sigma_1$ , $\sigma_2$ , $\sigma_3$ w jednokładności o środku $P$ i skali $t/s$ ; wynika to z równości:

$ |PK| = |PL| = |PM| = t, \quad |PK_0| - |PL_0| = |PM_0| = s. $

Obrazem płaszczyzny $\pi$ (czyli $A_0B_0C_0$ ) w tej jednokładności jest równoległa do niej płaszczyzna $ABC$ . Stąd wynika, że punkty $B$ i $C$ są wyznaczone jednoznacznie jako punkty przecięcia półprostych $l$ i $m$ z płaszczyzną równoległą do $\pi$ , przechodzącą przez punkt $A$ .

Na odwrót, określając punkty $B$ i $C$ w ten właśnie sposób, spełnimy warunki zadania, bowiem przedstawione w analizie rozumowanie można odwrócić: jednokładność, przeprowadzająca płaszczyznę $\pi$ do położenia, w którym przechodzi ona przez punkt $A$ , odwzorowuje okręgi $\sigma_1$ , $\sigma_2$ , $\sigma_3$ na okręgi $\omega_1$ , $\omega_2$ , $\omega_3$ , dopisane do trójkątów $PBC$ , $PCA$ , $PAB$ przy bokach $BC$ , $CA$ , $AB$ .

Oznaczając ich punkty styczności z tymi bokami odpowiednio przez $Q$ , $R$ , $S$ , a punkty styczności z półprostymi $k$ , $l$ , $m$ odpowiednio przez $K$ , $L$ , $M$ , oraz oznaczając przez $l$ wspólną długość odcinków $PK$ , $PL$ , $PM$ , uzyskujemy kolejno równości (9), (8) oraz (5), (6) i (7); z nich zaś - związki

$ |PA| + |AB| = |PA| + |AS| + |BS| = |PA| + |AK| + |BL| = t + |BL|, $

$ |PC| + |CB| = |PC| + |CQ| + |BQ| = |PC| + |CM| + |BL| = t + |BL| $

oraz

$ |PB| + |BC| = |PB| + |BQ| + |CQ| = |PB| + |BL| + |CM| = t + |CM|, $

$ |PA| + |AC| = |PA| + |AR| + |CR| = |PA| + |AK| + |CM| = t + |CM|. $

Spełnione są więc warunki (1); dowód jest zakończony.