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.