XXXVII OM - III etap

III etap XXXVII Olimpiady Matematycznej

XXXVII OM - III - Zadanie 1

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

Kwadrat o boku długości 1 pokryto $m^2$ prostokątami. Dowieść, że obwód pewnego z tych prostokątów jest większy lub równy $4/m$ .

Rozwiązanie

Pole $P = ab$ i obwód $p = 2(a+b)$ prostokąta o bokach długości $a$ , $b$ związane są nierównością

$ p^2 = 4(a + b)^2 = 4((a - b)^2 + 4ab) \geq 16P. $

Gdyby więc każdy z rozważanych $m^2$ prostokątów miał obwód mniejszy od
$4/m$ , to pole każdego z nich byłoby mniejsze od $\frac{1}{16} \cdot \left( \frac{4}{m} \right)^2$ (czyli od $1/m^2$ ), a więc suma ich pól byłaby mniejsza od $1$ - wbrew założeniu, że pokrywają one kwadrat jednostkowy.

XXXVII OM - III - Zadanie 2

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

Wyznaczyć maksimum objętości czworościanów mających trzy ściany o polu 1.

Rozwiązanie

Niech $ABCD$ będzie czworościanem, w którym $S_A = S_B = S_D = 1$ ; przez $S_X$ oznaczamy tu pole ściany nie zawierającej wierzchołka $X$ ( $X = A, B, C, D$ ). Dalej, oznaczmy

$ \begin{split} & a = |BC|, \ b=|CA|,\ y= |\measuredangle BCA|,\\ & u = \textrm{odległość wierzchołka}\ D \textrm{od prostej}\ BC,\\ & v = \textrm{odległość wierzchołka}\ D \textrm{od prostej}\ CA,\\ & h = \textrm{odległość wierzchołka}\ D \textrm{od płaszczyzny}\ ABC,\\ & \varphi = \textrm{miara kąta dwuściennego między płaszczyznami}\ ABC \ \textrm{i} \ BCD,\\ & \psi = \textrm{miara kąta dwuściennego między płaszczyznami}\ ABC \ \textrm{i} \ CAD,\\ & V = \textrm{objętość czworościanu}\ ABCD \end{split} $

(rysunek 10 przedstawia siatkę powierzchni czworościanu $ABCD$ rozwiniętej na płaszczyźnie $ABC$ ).

Zachodzą związki

$ (1) \qquad V = \frac{1}{3}S_Dh = \frac{1}{3}h, $

$ (2) \qquad h = u \sin \varphi = v \sin \psi, $

$ (3) \qquad 1 = S_A = \frac{1}{2} au,\ 1 = S_B = \frac{1}{2} bv,\ 1 = S_D=\frac{1}{2} ab \sin \gamma $

Z ostatnich równości wynika, że

$ uv = \frac{2}{a} \cdot \frac{2}{b} = 2 \sin \gamma, $

co po podstawieniu do (1) i uwzględnieniu (2) daje

$ V = \frac{1}{3} \sqrt{h \cdot h} = \frac{1}{3} \sqrt{u\sin \varphi \cdot v\sin \psi} = \frac{1}{3} \sqrt{2\sin \gamma \sin \varphi \sin \psi} \leq \frac{1}{3} \sqrt{2}. $

Na to, by otrzymana nierówność stała się równością potrzeba i wystarcza, żeby $\gamma = \varphi = \psi =90^\circ$ - przy jednoczesnym spełnieniu związków (3). To zaś ma miejsce wtedy i tylko wtedy, gdy krawędzie $CA$ , $CB$ , $CD$ są wzajemnie prostopadłe (rysunek 11) oraz długość każdej z nich wynosi $\sqrt{2}$ .

Szukane maksimum objętości $V$ równa się więc $\sqrt{2}/3$ .

XXXVII OM - III - Zadanie 3

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

Dowieść, że jeżeli $p$ jest liczbą pierwszą, a liczba całkowita $m$ spełnia nierówność $0 \leq m < p—1$ , to $p$ dzieli liczbę $\sum_{j=1}^p j^m$ .

Rozwiązanie

Oznaczmy sumę $1^m+2^m+ \ldots +p^m$ przez $A (p, m)$ . Mamy dowieść, że przy podanych w zadaniu założeniach

$ p|A(p, m). $

Dowód prowadzimy przez indukcję względem $m$ (przy ustalonym $p$ ). Gdy $m = 0$ , dostajemy liczbę $A (p, 0) = p$ , która oczywiście dzieli się przez $p$ .

Ustalmy liczbę całkowitą $m$ spełniającą warunek $0 < m < p - 1$ i załóżmy, że

$ (1) \qquad p|A(p,k)\ \textrm{dla} \ k = 0, \ldots ,m-1. $

Chcemy pokazać, że $p|A (p, m)$ .

Zgodnie z wzorem dwumianowym Newtona, dla każdej liczby naturalnej $j$ spełniona jest równość

$ (j+1)^{m+1} = \sum_{k=0}^{m+1} \binom{m+1}{k} j^k. $

Podstawiając $j =1, \ldots, p$ dostajemy stąd ciąg równości

$ \begin{split} (1+1)^{m+1} - 1^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 1^k,\\ (2+1)^{m+1} - 2^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 2^k,\\ (3+1)^{m+1} - 3^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} 3^k,\\ \ldots\\ (p+1)^{m+1} - p^{m+1} = \sum_{k=0}^{m} \binom{m+1}{k} p^k. \end{split} $

Dodając stronami otrzymujemy

$ \begin{split} (2) \qquad (p+1)^{m+1}-1 = \sum_{j=1}^p \sum_{k=0}^m \binom{m+1}{k} = \sum_{k=0}^m \binom{m+1}{k} \sum_{j=1}^p j^k = \\ = \sum_{k=0}^m \binom{m+1}{k} A(p,k) = (m+1)A(p,m) + \sum_{k=0}^{m-1} \binom{m+1}{k} A(p,k). \end{split} $

Lewą stronę równości (2) możemy przepisać w postaci $((p+1)-1) \times \sum_{k=0}^m (p+1)^k$ . Jest to liczba podzielna przez $p$ . W ostatniej sumie po prawej stronie równości (2) wszystkie składniki są podzielne przez $p$ , na mocy założenia indukcyjnego (1). Zatem i pozostały składnik występujący w (2) jest podzielny przez $p$ :

$ p|(m + 1)A(p,m). $

Ponieważ $p$ jest liczbą pierwszą, musi dzielić jeden z czynników otrzymanego iloczynu. Liczba $m + 1$ , jako mniejsza od $p$ , nie dzieli się przez $p$ . Zatem ostatecznie $p|A(p, m)$ , a to właśnie mieliśmy wykazać.

Na mocy zasady indukcji, podane w zadaniu twierdzenie jest udowodnione.

Uwaga. Wzór (2) stanowi formułę rekurencyjną, z której można obliczyć sumy potęg (o coraz większych wykładnikach naturalnych) skończonych ciągów kolejnych liczb naturalnych.

XXXVII OM - III - Zadanie 4

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

Wyznaczyć te liczby całkowite nieujemne $n$ , dla których istnieje taki wielomian $f$ stopnia $n$ o współczynnikach rzeczywistych, że $f(x) > f'(x)$ dla każdego rzeczywistego $x$ .

Rozwiązanie

Wykażemy, że żądaną własność mają wszystkie liczby parzyste (i tylko one).

Jeśli $f$ jest wielomianem stopnia $n > 0$ o podanej własności, to wówczas

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

jest także wielomianem stopnia $n$ , przy czym $g (x) \geq 0$ dla $x \in \mathbb{R}$ . Ponieważ każdy wielomian stopnia nieparzystego (o współczynnikach rzeczywistych) przyjmuje również wartości ujemne, $n$ musi być liczbą parzystą.

Gdy $n = 0$ , to oczywiście wielomian $f(x) = 1$ spełnia warunek $f(x)>f'(x) = 0$ .

Gdy $n$ jest liczbą parzystą dodatnią, bierzemy wielomian $h(x) = x^n$ . Różnica

$ h(x)-h'(x) = x^n - nx^{n-1} = x^{n-1}(x - n) $

jest dodatnia poza przedziałem $\langle 0; n \rangle$ , a dla $x \in \langle 0; n \rangle$ jej wartość bezwzględna nie przekracza $n^{n-1} \cdot n = n^n$ . Zatem wielomian $f(x) = h(x)+n^n$ spełnia żądany warunek

$ f(x)-f'(x) = n^n+h(x) - h'(x) \geq 0 \ \textrm{dla} \ x \in \mathbb{R}. $

XXXVII OM - III - Zadanie 5

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

W turnieju szachowym uczestniczy $2n$ ( $n > 1$ ) zawodników, przy czym każdych dwóch spośród nich rozgrywa między sobą co najwyżej jedną partię. Dowieść, że taki przebieg rozgrywek, w którym żadna trójka uczestników nie rozgrywa trzech partii między sobą jest możliwy wtedy i tylko wtedy, gdy liczba wszystkich partii rozegranych w turnieju nie przekracza $n^2$ .

Rozwiązanie

Mamy do udowodnienia równoważność następujących dwóch stwierdzeń $A$ i $B$ (dla danych liczb naturalnych $m$ i $n$ , $n > 1$ ):

A. Istnieje możliwość takiej organizacji rozgrywek turnieju z udziałem $2n$ zawodników, że

$A_1$ ) każdy z każdym gra co najwyżej jedną partię,
$A_2$ ) żadna trójka nie rozgrywa trzech partii między sobą,
$A_3$ ) łączna liczba partii w turnieju wynosi $m$ .

B. Liczby $m$ i $n$ spełniają nierówność $m \leq n^2$ .

Dowód implikacji $B \Longrightarrow A$ . Uczestników turnieju dzielimy w dowolny sposób na dwie grupy po $n$ zawodników. Liczba par, w których partnerzy należą do różnych grup, wynosi $n^2$ . Wybieramy dowolnie $m$ spośród tych par i przeprowadzamy rozgrywki w wybranych parach. Spełnienie warunków $A_1$ , $A_2$ , $A_3$ jest oczywiste.

Dowód implikacji $A \Longrightarrow B$ . Stosujemy indukcję względem $n$ . Gdy $n = 2$ , mamy $4$ graczy i $6$ możliwych par. Gdyby liczba rozgrywanych partii przekraczała $4$ , znaczyłoby to, że rozgrywane są wszystkie możliwe spotkania z wyjątkiem co najwyżej jednego; musi wtedy utworzyć się ,,trójkąt spotkań'' (a nawet dwa takie trójkąty).

Załóżmy, że twierdzenie jest prawdziwe dla pewnego $n \geq 2$ i przypuśćmy, że został zorganizowany turniej z udziałem $2(n + 1)$ zawodników tak, że spełnione są warunki $A_1$ , $A_2$ , $A_3$ . Mamy pokazać, że $m \leq (n + 1)^2$ . Wybierzmy dowolnych dwóch zawodników rozgrywających partię między sobą i nazwijmy ich $X$ i $Y$ . Liczba partii rozgrywanych między pozostałymi $2n$ zawodnikami nie przekracza $n^2$ , w myśl założenia indukcyjnego. Niech $x$ będzie liczbą partii rozgrywanych przez gracza $X$ (nie licząc spotkania z $Y$ ), a $y$ - liczbą partii rozgrywanych przez $Y$ (nie licząc spotkania z $X$ ). Wówczas $x + y \leq 2n$ ; w przeciwnym razie $X$ i $Y$ mieliby wspólnego przeciwnika i powstałby ,,trójkąt spotkań'', wbrew warunkowi $A_2$ . Uwzględniając jeszcze mecz pomiędzy $X$ i $Y$ widzimy, że łączna liczba spotkań w turnieju nie przekracza $n^2 + 2n + 1$ czyli $(n + 1)^2$ . Kończy to dowód indukcyjny.

XXXVII OM - III - Zadanie 6

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

III

W trójkącie $ABC$ punkty $K$ i $L$ są rzutami prostokątnymi wierzchołków $B$ i $C$ na dwusieczną kąta $BAC$ , punkt $M$ jest spodkiem wysokości trójkąta $ABC$ poprowadzonej z wierzchołka $A$ , a punkt $N$ jest środkiem boku $BC$ . Wykazać, że punkty $K$ , $L$ , $M$ i $N$ leżą na jednym okręgu.

Rozwiązanie

Gdy $|AB| = |AC|$ , punkty $K$ , $L$ , $M$ , $N$ pokrywają się. W dalszym ciągu wyłączymy ten trywialny przypadek z rozważań. Przedstawimy trzy sposoby rozwiązania.

\spos{I} Bez zmniejszania ogólności możemy zakładać, że $|AB| < |AC|$ . Przypuśćmy na początek, że kąt $ABC$ nie jest prosty - jest więc ostry lub rozwarty. Rysunki 12a i 12b ilustrują te dwie sytuacje.

Rozważmy okrąg, którego średnicą jest odcinek $AB$ . Ponieważ $|\measuredangle AKB| = | \measuredangle AMB| = 90^\circ$ , punkty $K$ i $M$ leżą na tym okręgu. Kąty wpisane $BAK$ i $KMB$ są oparte bądź na wspólnym łuku (gdy $|\measuredangle B| > 90^\circ$ - rys. 12b), bądź na łukach dopełniających się do pełnego okręgu (gdy $|\measuredangle B | < 90^\circ$ - rys. 12a). Tak więc

$ |\measuredangle BAK| = \left\{ \begin{array}{cll} |180^\circ - |\measuredangle KMB| & \textrm{gdy} & |\measuredangle B| < 90^\circ \\ |\measuredangle KMB| & \textrm{gdy} & |\measuredangle B| > 90^\circ \end{array} \right. $

W obu przypadkach wyrażenie otrzymane po prawej stronie jest równe mierze kąta $KMN$ . Zatem

$ (1) \qquad |\measuredangle BAK| = |\measuredangle KMN|. $

Gdy kąt $ABC$ jest prosty, punkt $M$ pokrywa się z $B$ , a kąty $BAK$ i $KMN$ mają ramiona odpowiednio prostopadłe. Tak więc równość (1) zachodzi i w tym przypadku.

Przedłużmy bok $AB$ do przecięcia z prostą $CL$ w punkcie, który oznaczymy przez $E$ . Odcinek $AL$ jest jednocześnie dwusieczną i wysokością w trójkącie $ACE$ ; jest więc to trójkąt równoramienny i punkt $L$ jest środkiem boku $CE$ . Zatem odcinek $NL$ , jako łączący środki boków $BC$ i $CE$ trójkąta $BCE$ , jest równoległy do boku $BE$ , czyli do prostej $AB$ . Stąd $|\measuredangle BAK| = |\measuredangle KLN|$ . W połączeniu z równością (1) daje to równość $|\measuredangle KMN| = |\measuredangle KLN|$ , z której wynika, że punkty $K$ , $N$ , $L$ , $M$ leżą na jednym okręgu.