XIX OM - III - Zadanie 1

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),<br /> (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

\[<br /> \ne{1} f(k+1)=f(k) + 4k + 2.<br /> \]

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

\[<br /> \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).<br /> \]

Stąd otrzymujemy

\[<br /> f(n)=f(1) + 4 \cdot \frac{1}{2} n(n- 1) + 2n-2,<br /> \]

a po uproszczeniu

\[<br /> f(n) = 2n^2 + 1.<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź