XIX OM - III etap

III etap XIX Olimpiady Matematycznej

XIX OM - III - Zadanie 1

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Jaka jest największa liczba obszarów, na które można podzielić płaszczyznę prowadząc $n$ par prostych równoległych?

Rozwiązanie

Niech $f(n)$ oznacza największą liczbę obszarów, na jakie może podzielić płaszczyznę $n$ par prostych równoległych.

Obierzmy na płaszczyźnie $k + 1$ par prostych równoległych $(p_1,q_1), (p_2, q_2), \ldots, (p_k, q_k), (p_{k+1}, q_{k+1})$ .

Przypuśćmy, że $(p_1, q_1), (p_1, q_2),\ldots (p_k,q_k)$ dzielą płaszczyznę na $l$ obszarów, oraz że prosta $p_{k+1}$ przecina proste tych $k$ par w $r$ punktach, a prosta $q_{k+1}$ - w $s$ punktach. Wówczas $0 \leq r \leq 2k$ , $0 \leq s \leq 2k$ , przy czym równości $r = 2k$ , $s = 2k$ zachodzą dokładnie wtedy, gdy zarówno prosta $p_{k+1}$ jak prosta $q_{k+1}$ przecina każdą z prostych $p_1, q_1, p_2, q_2, \ldots, p_k,q_k$ ale nie przechodzi przez żaden punkt przecięcia tych prostych.

Owe $r$ punktów dzieli prostą $p_{k+1}$ , na $r+1$ części. Każda z tych części jest odcinkiem lub półprostą, a gdy $r = 0$ - całą prostą, leży w jednym z $l$ obszarów, na jakie proste $p_1, q_1, p_2, q_2, \ldots, p_k, q_k$ dzielą płaszczyznę (przy czym każda część leży w innym obszarze) i rozcina go na dwa obszary. Proste $p_1, q_1, p_2, q_2,\ldots,p_k, q_k$ oraz $p_{k+1}$ dzielą zatem płaszczyznę na $l + r + 1$ obszarów. Podobnie $s$ punktów prostej $q_{k+1}$ dzieli tę prostą na $s + 1$ części, z których każda rozcina jeden z poprzednich $l + r + 1$ obszarów na dwa obszary. Wszystkie proste $p_1, q_1, p_2, q_2, \ldots, p_k, q_k, p_{k+1}, q_{k + 1}$ dzielą zatem płaszczyznę na $l + r + s + 2$ obszarów.

Liczba ta jest największa wtedy, gdy wartości $l$ , $r$ i $s$ są największe, tj. gdy $l=f(k)$ , $r = 2k$ , $s = 2k$ . Zatem

$ \ne{1} f(k+1)=f(k) + 4k + 2. $

Otóż $f(1) = 3$ ; ze wzoru (1) otrzymujemy kolejne wartości $f(2) = 3 + 4 + 2=9$ , $f(3) = 9 + 8 + 2= 19$ itd.

Wartość $f(n)$ dla dowolnego naturalnego $n$ możemy obliczyć, podstawiając do (1) $k = 1, 2, \ldots, n - 1$ i dodając otrzymane równości

$ \sum_{k=1}^{n-1} f(k + 1) = \sum_{k=1}^{n-1} f(k) + 4\sum_{k=1}^{n-1} k + 2(n- 1). $

Stąd otrzymujemy

$ f(n)=f(1) + 4 \cdot \frac{1}{2} n(n- 1) + 2n-2, $

a po uproszczeniu

$ f(n) = 2n^2 + 1. $

XIX OM - III - Zadanie 2

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Dowieść, że dla każdego naturalnego $n$

$ (1) \quad \frac{1}{3} + \frac{2}{3\cdot 5} + \frac{3}{3 \cdot 5 \cdot 7} + \ldost + \frac{n}{3 \cdot 5 \cdot 7 \cdot \ldots \cdot (2n+1)} < \frac{1}{2}. $

Rozwiązanie

Wprowadźmy oznaczenie

$ a_k = \frac{k}{3 \cdot 5 \cdot 7 \cdot \ldots \cdot (2k + 1)}. $

Zauważmy, że

$ \frac{1}{2} - a_1 = \frac{1}{2} - \frac{1}{3} = \frac{1}{2 \cdot 3},\ \frac{1}{2} (a_1+a_2) = \frac{1}{2} - \left(\frac{1}{3} + \frac{2}{3 \cdot 5} \right) = \frac{1}{2 \cdot 3 \cdot 5}. $

Nasuwa się przypuszczenie, że dla każdego naturalnego $n$

$ (2) \qquad \frac{1}{2} - (a_1 + a_2 + \ldots + a_n) = \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n+1)}. $

Równość (2) łatwo udowodnić metodą indukcji. Z założenia, że równość (2) zachodzi, gdy $n$ równa się pewnej liczbie naturalnej $k$ wynika, że

$ \begin{split} \frac{1}{2} - (a_1 + a_2 &+ \ldots + a_k + a_{k+1}) =\\ &= \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)}- \frac{k+1}{3 \cdot 5 \cdot 7 \cdot \ldots \cdot (2k+3)} =\\ &=\frac{2k + 3 - 2(k+1)}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+3)}= \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+3)}, \end{split} $

tzn., że równość (2) zachodzi także, gdy $n = k + 1$ . Stąd oraz z tego, że równość (2) jest prawdziwa, gdy $n = 1$ , wnioskujemy, że jest ona prawdziwa dla każdego naturalnego $n$ .

Z (2) wynika, że

$ a_1 + a_2+ \ldots +a_n < \frac{1}{2} $

dla każdego naturalnego $n$ , c.n.d.

Uwaga. Dowód nierówności (1) można również oprzeć na tym, że

$ (3) \qquad \begin{split} \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k-1)} - \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} =\\ =\frac{2k}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} = 2 a_k. \end{split} $

Dodając stronami równości (3) dla wartości $k$ od $1$ do $n$ otrzymujemy

$ (4) \qquad 2 \sum_{k=1}^n a_k = \sum_{k=1}^n \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k-1)} - \sum_{k=1}^n \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} . $

Zauważmy, że po prawej stronie równości (4) kolejne wyrazy pierwszej sumy począwszy od drugiego aż do $n$ -go są odpowiednio równe kolejnym wyrazom drugiej sumy od pierwszego do $(n - 1)$ -go; po redukcji równość (4) otrzymuje postać

$ 2 \sum_{k=1}^n a_k = 1 - \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} , $

skąd

$ (5) \qquad \sum_{k=1}^n a_k = \frac{1}{2} - \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)}. $

Z (5) wynika, że

$ \sum_{k=1}^n a_k < \frac{1}{2}, $

czego należało dowieść.

XIX OM - III - Zadanie 3

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

W czworościanie $ABCD$ krawędzie $AD$ , $BD$ , $CD$ są równe. Na płaszczyźnie $ABC$ obrano punkty niewspółliniowe $A_1, B_1, C_1$ Proste $DA_1, DB_1, DC_1$ przecinają powierzchnię kuli opisanej na czworościanie odpowiednio w punktach $A_2, B_2, C_2$ , różnych od punktu $D$ . Udowodnić, że punkty $A_1, B_1, C_1, A_2, B_2, C_2$ leżą na powierzchni pewnej kuli.

Rozwiązanie

Sfera (tj. powierzchnia kuli) $S$ opisana na czworościanie $ABCD$ przecina płaszczyznę $ABC$ wzdłuż okręgu $k$ opisanego na trójkącie $ABC$ . Z równości $DA = DB = DC$ wynika, że sfera $t$ o środku $D$ i promieniu $r = DA$ przechodzi przez punkty $B$ i $C$ , więc przecina sferę $s$ i płaszczyznę $ABC$ wzdłuż tego samego okręgu $k$ . Wobec tego rzut prostokątny $H$ punktu $D$ na płaszczyznę $ABC$ jest środkiem okręgu $k$ . Płaszczyzna $A_1HD$ zawiera zatem pewną średnicę $MN$ okręgu $k$ i przecina sferę $s$ wzdłuż okręgu $l$ przechodzącego przez punkty $M$ , $N$ i $D$ (rys. 16).

Według twierdzenia o potędze punktu względem okręgu

$ A_1 A_2 \cdot A_1D = A_1M \cdot A_1N. $

Stąd

$ (A_1 D - A_2D) \cdot A_1D = (A_1H- MH) (A_1H + MH) = A_1G^2 - MH^2, $

więc

$ A_1D \cdot A_2D = A_1D^2 - A_1H^2 + MH^2 = HD^2 + MH^2 = MD^2. $

Równość tę można zapisać w postaci

$ (1) \qquad DA_1 \cdot DA_2 = r^2. $

Analogicznie

$ (2) \qquad DB_1 \cdot DB_2 = r^2. $

Z (1) i (2) wynika

$ (3) \qquad DA_1 \cdot DA_2 = DB_1 \cdot DB_2. $

Z równości (3) oraz z tego, że pary punktów $A_1$ , $A_2$ , i $B_1$ , $B_2$ leżą na dwóch różnych półprostych o początku $D$ nie tworzących jednej prostej, łatwo wywnioskować, że punkty $A_1$ , $A_2$ , $B_1$ , $B_2$ , leżą na okręgu.

Istotnie, niech $m$ będzie okręgiem przechodzącym przez punkty niewspółliniowe $A_1$ , $A_2$ , $B_1$ (rys. 17).

Punkt $D$ leży na zewnątrz okręgu $m$ , zatem

$ (4) \qquad DA_1 \cdot DA_2 = DB_1 \cdot DX, $

gdzie $X$ jest punktem wspólnym okręgu $m$ z półprostą $DB_1$ .

Z (3) i (4) otrzymujemy

$ DX = DB_2, $

a ponieważ punkty $X$ i $B_2$ należą do tej samej półprostej o początku $D$ , więc punkt $X$ pokrywa się z punktem $B_2$ .

Analogicznie stwierdzamy, że punkty $B_1$ , $B_2$ , $C_1$ , $C_2$ leżą na pewnym okręgu $n$ .

Okręgi $m$ i $n$ mają punkty wspólne $B_1$ i $B_2$ , a przy tym leżą w rożnych płaszczyznach, gdyż według założenia punkty wspólne tych okręgów z płaszczyzną $ABC$ , tj. punkty $A_1$ , $B_1$ , $C_1$ nie są współliniowe.

Stąd wynika, że okręgi $m$ i $n$ , a tym samym punkty $A_1$ , $B_1$ , $C_1$ , $A_2$ , $B_2$ , $C_2$ leżą na jednej sferze, c.n.d.

Uwaga. Początek powyższego dowodu można znacznie skrócić, powołując się na własności przekształcenia przez inwersję. Mianowicie w inwersji względem sfery o środku $D$ i promieniu $r = DA$ przecinającej płaszczyznę $ABC$ wzdłuż okręgu $k$ obrazem płaszczyzny $ABC$ jest sfera przechodząca przez środek inwersji $D$ i przez okrąg $k$ , tj. sfera $s$ . Obrazami punktów $A_1$ , $B_1$ , $C_1$ są zatem odpowiednio punkty $A_2$ , $B_2$ , $C_2$ , wobec czego

$ DA_1 \cdot DA_2 = DB_1 \cdot DB_2 = DC_1 \cdot DC_2 = r^2. $

Dalszy ciąg dowodu pozostaje ten sam co poprzednio.

XIX OM - III - Zadanie 4

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Dana jest liczba naturalna $n>2$ . Podać taki zbiór $n$ liczb naturalnych $a_1, a_2, \ldots, a_n$ , żeby w zbiorze sum

$ a_i + a_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j) $

było możliwie najmniej liczb różnych oraz taki zbiór $n$ liczb naturalnych $b_1, b_2, \ldots, b_n$ , żeby w zbiorze sum

$ b_i + b_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j) $

było możliwie najwięcej liczb różnych.

Rozwiązanie

Gdy $Z$ jest skończonym zbiorem liczb, umówimy się oznaczać symbolem $l(Z)$ liczbę różnych wartości, jakie mają sumy dwóch liczb należących do $Z$ .

1) Niech $A$ będzie zbiorem $n > 2$ liczb naturalnych $a_i$ ( $i = 1,2,\ldots, n$ ) tak oznaczonych, że

$ (1) \qquad a_1 < a_2 < \ldots < a_n. $

Ponieważ

$ (2) \qquad a_1 + a_2 < a_1 + a_3< \ldots < a_1 + a_n < a_2 + a_n < a_3 + a_n < \ldots < a_{n-1} + a_n, $

więc w zbiorze sum $a_i + a_j$ jest co najmniej $2n - 3$ liczb różnych, tj. $l(A) \geq 2n - 3$ .

Jeśli zatem utworzymy taki zbiór $A$ , że $l(A) = 2n - 3$ , będzie to zbiór jakiego poszukujemy. Trzeba w tym celu dobrać liczby $a_1, a_2, \ldots, a_n$ w taki sposób, żeby każda suma $a_i + a_j$ była równa którejś z sum występujących w (2), tzn. jednej z sum $a_1 + a_j$ ( $j = 2,3, \ldots,n$ ), lub jednej z sum $a_i + a_n$ ( $i = 2,3,\ldots, (n-1)$ ).

Wykażemy, że przypadek taki zachodzi, gdy liczby zbioru $A$ tworzą postęp arytmetyczny.

Załóżmy, że

$ a_2 - a_1 = a_3 - a_2 = \ldots = a_n - a_{n-1} = d > 0. $

Według znanych wzorów

$ (3) \qquad a_k = a_1 + (k-1)d= a_n- (n-k)d \textrm{ dla } k = 1,2 \ldots, n. $

Rozpatrzmy sumę $a_i + a_j$ , gdzie $1 \leq i < j \leq n$ .

Gdy $i + j \leq n$ , wtedy na mocy (3)

$ (4) \qquad a_i + a_j = a_1 + (i - 1) d + a_1 + (j- 1)d = a_1 + [a_1 + (i+j+2)d] = a_1 + a_{i+j-1}; $

gdy zaś $i + j>n$ , wtedy według (3)

$ (5) \qquad a_i + a_j = a_1 + (i - 1)d + a_n - (n - j) d = a_n + [a_1 + (i + j - n - 1)d] = a_{i+j-n} + a_n. $

Z (4) i (5) wynika, że każda suma $a_i + a_j$ jest równa jednej z sum (2), zatem $l(A) = 2n - 3$ , c.n.d.

b) Zbiór liczb naturalnych $B = \{ b_1, b_2, \ldots , b_n\}$ o możliwie największej liczbie $l(B)$ różnych wartości sum $b_i + b_j$ ( $i,j= 1,2,\ldots, n$ , $i \ne j$ ), uzyskamy wtedy, gdy wszystkie sumy $b_i + b_j$ , będą różnymi liczbami; wówczas $l (B) = \frac{1}{2} n (n - 1)$ .

Zbiorem takim jest na przykład zbiór wyrazów postępu geometrycznego

$ (6) \qquad 1, q, q^2, \ldots, q^{n-1}, $

którego iloraz $q$ jest liczbą naturalną większą od $1$ .

Przypuśćmy bowiem, że dla pewnych wyrazów ciągu (6) zachodzi równość

$ (7) \qquad q^i + q^j= g^k + q^l, \textrm{ gdzie } i < j,\ k < l; $

wtedy

$ (8) \qquad q^i (1 + q^{j-i}) = q^k (1 + q^{l-k}). $

Ponieważ liczby $1 + q^{j-i}$ i $1 + q^{l-k}$ są pierwsze względem $q$ , więc z równości (8) wynika, że $q^k$ jest podzielne przez $q^i$ , a $q^i$ przez $q^k$ . Zatem $k = i$ , a wobec (7) także $l = j$ , tzn. równość (7) nie może zachodzić, gdy $q^i$ , $q^j$ nie są tymi samymi wyrazami ciągu (6), co $q^k$ , $q^l$ .

Uwaga 1. Niech $A$ będzie zbiorem liczb $a_1 < a_2< \ldots < a_n$ ( $n > 2$ ), dla którego liczba $l (A)$ różnych wartości sum $a_i + a_j$ wynosi $2n - 3$ , czyli jest możliwie najmniejsza. Postawimy pytanie, czy ciąg $a_1, a_2, \ldots, a_n$ musi być postępem arytmetycznym?

Łatwo zauważyć, że tak nie jest, gdy $n = 3$ , ani gdy $n = 4$ . Z nierówności $a_1 < a_2 < a_3$ wynika bowiem, że $a_1 + a_2 < a_1 + a_3 < a_2 + a_3$ więc dla zbioru $A$ trzech różnych liczb zawsze $l(A) = 3$ . Aby zaś dla zbioru $A$ liczb $a_1 < a_2< a_3< a_4$ było $l(A) = 5$ , trzeba tylko, żeby zachodziła równość $a_4 - a_3 = a_2 - a_1$ .

Udowodnimy, że gdy $n \geq 5$ , wtedy każdy zbiór $A$ złożony z $n$ liczb, dla którego $l(A) = 2n - 3$ , jest zbiorem wyrazów postępu arytmetycznego.

Dla $n = 5$ teza tego twierdzenia jest prawdziwa. Istotnie, gdy dany jest zbiór $A$ pięciu liczb

$ (1) \qquad a_1 < a_2 < a_3 < a_4 < a_5, $

wtedy

$ (2) \qquad a_1 + a_2 < a_1 + a_3 < a_1 + a_4 < a_1 + a_5 < a_2 + a_5 < a_3 + a_5 < a_4 + a_5 $

$ (3) \qquad a_2 + a_3 < a_2 + a_4 < a_3 + a_4, $

więc jeśli $l(A) = 2 \cdot 5 - 3 = 7$ , to każda z sum występujących w (3) musi być równa jednej z siedmiu sum występujących w (2). Ponieważ zaś każda z sum (3) jest większa niż $a_1 + a_3$ , a mniejsza niż $a_3 + a_5$ , więc zachodzą równości

$ a_2 + a_3 = a_1 + a_4, \ a_2 + a_4 = a_1 + a_5, \ a_3 + a_4 = a_2 + a_5, $

z których wynika, że

$ a_2 - a_1 = a_4 - a_3,\ a_2 - a_1 = a_5 - a_4, a_3 - a_2 = a_5 - a_4, $

co oznacza, że ciąg (1) jest postępem arytmetycznym.

Załóżmy, że teza twierdzenia jest prawdziwa dla pewnego $n \geq 5$ . Niech $A$ będzie zbiorem liczb

$ (4) \qquad a_1 < a_2 < \ldots < a_n < a_{n+1}, $

dla którego $l(A) = 2(n + 1) - 3$ .

Weźmy pod uwagę zbiory

$ A' = \{ a_1, a_2,\ldots,a_n \}, $

$ A'' = \{ a_2, a_3,\ldots,a_n, a_{n+1} \}. $

Wykażemy, że

$ l(A') = l(A'') = 2n - 3. $

Istotnie, jeśli liczby $a_i$ , $a_j$ ( $i< j$ ) zbioru $A$ należą do zbioru $A'$ , to

$ a_i + a_j < a_{n-1} + a_{n+1} < a_n + a_{n + 1}, $

więc liczba różnych wartości sum $a_i + a_j$ jest dla zbioru $A'$ co najmniej o $2$ mniejsza niż dla zbioru $A$ , tj.

$ l(A') \leq l(A) - 2 = 2n - 3. $

Wiemy zaś, że

$ l(A') \geq 2n - 3. $

Zatem $l(A') = 2n - 3$ .

Podobnie, jeśli liczby $a_i$ , $a_j$ ( $i < j$ ) zbioru $A$ należą do zbioru $A''$ , to

$ a_i + a_j > a_1 + a_3 > a_1 + a_2, $

skąd wynika, że $l(A'') \leq l(A) - 2 = 2n - 3$ , a że $l(A'') \geq 2n - 3$ , więc $l(A'') = 2n - 3$ .

Na mocy założenia indukcyjnego ciągi $a_1, a_2, \ldots, a_n$ i $a_2, a3,\ldots, a_{n+1}$ są postępami arytmetycznymi, a wobec tego ciąg $a_1, a_2, \ldots, a_n, a_{n+1}$ jest również postępem arytmetycznym, tzn. teza twierdzenia jest prawdziwa dla zbiorów złożonych z $n + 1$ liczb. Według zasady indukcji jest ona tedy prawdziwa dla każdego naturalnego $n \geq 5$ .

Uwaga 2. Przykładów takiego zbioru $B = \{b_1, b_2,\ldots, b_n \}$ , że $l(B) = \frac{1}{2} n(n-1)$ można podać wiele. Własność tę ma np. zbiór $n$ kolejnych wyrazów ciągu Fibonacci'ego *), tj. ciągu liczb $b_n$ określonego wzorami $b_1 =0$ , $b_2 = 1$ , a dla każdego $n > 2$ $b_n = b_{n-1}+ b_{n-2}$ .

Pierwszymi wyrazami tego ciągu są zatem liczby $0, 1, 1, 2, 3, 5, 8, 13, \ldots$ .

Dowód, że każda z sum $b_i + b_j$ jest inną liczbą, łatwo przeprowadzić metodą indukcji.

XIX OM - III - Zadanie 5

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Na płaszczyźnie leży $n$ punktów ( $n \geq 4$ ), z których każde cztery są wierzchołkami czworokąta wypukłego. Dowieść, że wszystkie te punkty są wierzchołkami wielokąta wypukłego.

Rozwiązanie

Zastosujemy metodę indukcji. Gdy $n = 4$ , teza twierdzenia jest prawdziwa. Załóżmy, że teza twierdzenia jest prawdziwa dla pewnego naturalnego $n \geq 4$ , i niech $A_1, A_2, \ldots, A_n, A_{n+1}$ będą takimi $n + 1$ punktami płaszczyzny, że każde cztery z nich są wierzchołkami wielokąta wypukłego. Według założenia indukcyjnego punkty $A_1, A_2, \ldots, A_n$ są wierzchołkami wielokąta wypukłego $W$ . Przyjmiemy, że są to wierzchołki kolejne, co można uzyskać przez odpowiednią numerację punktów. Punkt $A_{n+1}$ nie leży na obwodzie wielokąta $W$ , gdyż żadne trzy dane punkty nie są współliniowe. Nie leży on także wewnątrz wielokąta $W$ , gdyż każdy punkt wewnętrzny wielokąta należy do jednego z trójkątów, na jakie można podzielić wielokąt jego przekątnymi, a punkt $A_{n + 1}$ nie może się znajdować w takim trójkącie. Zatem punkt $A_{n+1}$ leży na zewnątrz wielokąta $W$ . Weźmy pod uwagę kąty wypukłe o wierzchołku $A_{n+1}$ , których ramiona przechodzą przez wierzchołki wielokąta $W$ . Zbiór tych kątów jest skończony, więc istnieje wśród nich kąt największy. Niech to będzie na przykład kąt $\alpha = A_kA_{n + 1}A_l$ . Wewnątrz kąta $\alpha$ leżą wszystkie wierzchołki wielokąta $W$ oprócz $A_k$ i $A_l$ . W trójkącie $T$ o wierzchołkach $A_k$ , $A_{n+1}$ , $A_l$ nie leży żaden z wierzchołków $A_i$ wielokąta $W$ , różnych od $A_k$ i $A_l$ , gdyż punkty $A_i$ , $A_k$ , $A_l$ , $A_{n+1}$ są według założenia wierzchołkami czworokąta wypukłego. Wobec tego $A_k$ i $A_l$ są kolejnymi wierzchołkami wielokąta $W$ , np. $l=k+1$ . W takim razie punkty $A_1, A_2 \ldots A_k, A_{n+1}, A_{k+1}, \ldots, A_n$ są kolejnymi wierzchołkami wielokąta $W_1$ , który składa się z wielokąta $W$ i z trójkąta $T$ .

Dowiedziemy, że wielokąt $W_1$ jest wypukły, tj. że każdy odcinek którego końce leżą w wielokącie $W_1$ zawiera się cały w tym wielokącie. Istotnie, jeżeli punkty $M$ i $N$ leżą w wielokącie $W_1$ , to zachodzi jeden z przypadków: a) Punkty $M$ i $N$ leżą oba w wielokącie wypukłym $W$ , albo oba w trójkącie $T$ ; wtedy cały odcinek $MN$ zawiera się w wielokącie $W$ albo w trójkącie $T$ , a tym samym zawiera się w wielokącie $W_1$ ; b) Jeden z tych punktów, np. punkt $M$ , leży w wielokącie $W$ , a punkt $N$ w trójkącie $T$ . Odcinek $MN$ przecina wtedy obwód trójkąta $T$ w pewnym punkcie $P$ . Punkt $P$ leży na tej części obwodu trójkąta $T$ , która znajduje się w kącie $\alpha$ , tj. na odcinku $A_kA_{k+1}$ . Odcinek $MP$ należy więc do wielokąta $W$ , a odcinek $PN$ - do trójkąta $T$ ; każdy z tych odcinków, zatem także ich suma $MN$ , należy do wielokąta $W_1$ . Dowód indukcyjny twierdzenia został przeprowadzony.

Uwaga. Bardzo prosty dowód twierdzenia uzyskamy opierając się na twierdzeniu następującym:

Dla każdego skończonego zbioru $Z$ punktów płaszczyzny, składającego się z $n \geq 3$ punktów nie leżących na jednej prostej, istnieje taki wielokąt wypukły $W$ , że

1. Zbiór $Z$ jest zawarty w wielokącie $W$ .

2. Każdy wierzchołek wielokąta $W$ należy do zbioru $Z$ .

Taki wielokąt $W$ nazywa się oponą zbioru $Z$ *)

Niech $Z$ będzie zbiorem $n \geq 4$ punktów płaszczyzny, którego każde $4$ punkty są wierzchołkami czworokąta wypukłego i niech wielokąt $W$ będzie oponą zbioru $Z$ . Wówczas każdy punkt zbioru $Z$ jest wierzchołkiem wielokąta $W$ . Albowiem: $1^\circ$ żaden punkt zbioru $Z$ nie leży na obwodzie wielokąta $W$ między dwoma jego wierzchołkami, gdyż w zbiorze $Z$ nie ma trzech punktów współliniowych; $2^\circ$ żaden punkt zbioru $Z$ nie leży wewnątrz wielokąta $W$ , gdyż wówczas leżałby w jednym z trójkątów, na jakie można $W$ podzielić przekątnymi, a to byłoby również sprzeczne z założeniem. Opona $W$ jest zatem tym wielokątem, którego istnienia należało dowieść.

XIX OM - III - Zadanie 6

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Dany jest zbiór $n > 3$ punktów, z których żadne trzy nie są współliniowe, oraz liczba naturalna $k < n$ . Udowodnić twierdzenia:
1. Jeżeli $k \leq \frac{n}{2}$ , to każdy punkt danego zbioru można połączyć z co najmniej $k$ innymi punktami zbioru w taki sposób, że wśród poprowadzonych odcinków nie ma trzech boków tego samego trójkąta.
2. Jeżeli $k > \frac{n}{2}$ i każdy punkt danego zbioru jest połączony z $k$ innymi punktami zbioru, to wśród poprowadzonych odcinków są trzy boki tego samego trójkąta.

Rozwiązanie

$1^\circ$ . Załóżmy, że $k \leq \frac{n}{2}$ . Wybierzmy z danego zbioru $Z$ część $Z_1$ składającą się z $\left[ \frac{n}{2} \right]$ punktów*); część pozostała $Z_2$ zawiera $\left[ \frac{n}{2} \right]$ punktów, gdy $n$ jest parzyste, a $\left[ \frac{n}{2} \right]+ 1$ punktów, gdy $n$ jest nieparzyste. Ponieważ $k$ jest liczbą całkowitą, więc z warunku, że $k \leq \frac{n}{2}$ wynika, że $k \leq \left[ \frac{n}{2} \right]$ . Zatem każdy ze zbiorów $Z_1$ , $Z_2$ zawiera co najmniej $k$ punktów.

Połączmy odcinkami każdy punkt zbioru $Z_1$ z każdym punktem zbioru $Z_2$ . Wówczas każdy punkt zbioru $Z$ zostanie połączony z co najmniej $k$ innymi punktami tego zbioru. Żadne trzy z poprowadzonych odcinków nie są bokami tego samego trójkąta, gdyby bowiem taki trójkąt istniał, wtedy dwa jego wierzchołki, tj. oba końce jednego z odcinków, leżałyby w jednym ze zbiorów $Z_1$ , $Z_2$ , co jest niemożliwe, gdyż żaden taki odcinek nie został poprowadzony.

$2^\circ$ Załóżmy, że $k > \frac{n}{2}$ i że każdy punkt danego zbioru łączy $k$ odcinków z $k$ innymi punktami zbioru; niech $AB$ będzie jednym z poprowadzonych odcinków.

Z każdego z punktów $A$ i $B$ wychodzi oprócz $AB$ jeszcze $k - 1$ innych odcinków, czyli razem $2k - 2$ odcinków, których końce należą do zbioru pozostałych $n - 2$ punktów. Lecz jeśli $k > \frac{n}{2}$ , to $2k - 2 > n - 2$ ; wśród owych $2k - 2$ odcinków istnieją więc dwa odcinki o wspólnym końcu $C$ . W zbiorze poprowadzonych odcinków znajdują się zatem boki $AB$ , $AC$ i $BC$ trójkąta $ABC$ .

Uwaga. W podobny sposób można udowodnić twierdzenie ogólniejsze. Niech będą dane: zbiór $Z$ złożony z $n > 3$ punktów, z których żadne trzy nie są współliniowe, liczba naturalna $p$ spełniająca nierówności $3 \leq p < n$ oraz liczba naturalna $k < n$ . Wtedy:

$1 ^\circ$ Jeżeli $k \leq \frac{p-2}{p-1}n$ , wtedy każdy z punktów zbioru $Z$ można tak połączyć odcinkami z co najmniej $k$ innymi punktami tego zbioru, że w każdym podzbiorze zbioru $Z$ złożonym z $p$ punktów któreś dwa punkty nie są połączone odcinkiem.

$2^\circ$ Jeżeli $k > \frac{p-2}{p-1}n$ i każdy punkt zbioru $Z$ jest połączony odcinkiem z $k$ innymi punktami tego zbioru, wtedy istnieje taki podzbiór zbioru $Z$ złożony z $p$ punktów, w którym każde dwa punkty są połączone odcinkiem.