XXVIII - II - Zadanie 6

Zawody matematyczne:

XXVIII OM, 1976-1977

Etap:

Jaka jest największa liczba części, na które mogą rozciąć płaszczyznę brzegi $n$ kwadratów?

Rozwiązanie

Część wspólna brzegów dwóch kwadratów albo jest skończonym zbiorem punktów (i wtedy tych punktów jest co najwyżej $8$ , ponieważ każdy bok jednego kwadratu może przecinać brzeg drugiego kwadratu w co najwyżej dwóch punktach), albo zawiera odcinek (i wtedy jest odcinkiem, sumą dwóch odcinków - równoległych lub prostopadłych, lub jest sumą odcinka i punktu - rys. 11). W każdym więc przypadku ta część wspólna składa się z co najwyżej ośmiu spójnych części, z których każda jest punktem, odcinkiem lub sumą dwóch odcinków o wspólnym końcu.

Niech danych będzie na płaszczyźnie $n$ kwadratów $K_1, K_2, \ldots, K_n$ , gdzie $n$ jest pewną liczbą naturalną. Przypuśćmy, że brzegi tych kwadratów rozcięły płaszczyznę na $a_n$ części. Rysujemy teraz $(n + 1)$ kwadrat $K_{n+1}$ . Brzeg każdego z $n$ danych kwadratów $K_i$ wyznacza na brzegu kwadratu $K_{n+1}$ figurę $F_i$ złożoną z co najwyżej ośmiu spójnych części. Figura $F = F_1 \cup F_2 \cup \ldots \cup F_n$ składa się więc z co najwyżej $8n$ spójnych części (będących punktami, odcinkami lub sumami odcinków o wspólnych końcach). Wobec tego różnica brzegu kwadratu $K_{n+1}$ i figury $F$ składa się z co najwyżej $8n$ spójnych części będących odcinkami lub sumami odcinków. Każda taka część brzegu kwadratu $K_{n+1}$ dzieli na dwie części jedną z części płaszczyzny otrzymanych po narysowaniu kwadratów $K_1, K_2, \ldots, K_n$ . Wobec tego liczba $a_{n+1}$ części, na jakie rozcinają płaszczyznę brzegi kwadratów $K_1, K_2, \ldots, K_n, K_{n+1}$ spełnia

$ (1) \qquad a_{n+1} \leq a_n + 8n. $

Mamy oczywiście $a_1 = 2$ , ponieważ brzeg jednego kwadratu rozcina płaszczyznę na dwie części. Wobec tego ze wzoru (1) przez łatwą indukcję wynika, że dla dowolnej liczby naturalnej $k$ zachodzi

$ a_k < 2 + 8 \cdot 1 + 8 \cdot 2 + \ldots + 8 \cdot (k - 1), $

gdzie $a_k$ jest liczbą części, na jakie rozcinają płaszczyznę brzegi pewnych $k$ kwadratów. Przekształcając prawą stronę tego wzoru otrzymujemy

$ 2 + 8(1+2 + \ldots + (k-1)) = 2 + 8 \cdot \frac{k(k-1)}{2} = 2 + 4k^2 - 4k = (2k - 1)^2 + 1, $

czyli ostatecznie

$ (2) \qquad a_n \leq (2k-1)^2 + 1 \ \textrm{dla} \ k = 1,2,\ldots. $

Udowodnimy teraz, że dla dowolnej liczby naturalnej $n$ istnieje takich $n$ kwadratów, których brzegi rozcinają płaszczyznę na $(2n - 1)^2 + 1$ części, tzn. we wzorze (2) zachodzi równość. Weźmy mianowicie dowolnych $n + 1$ kwadratów $K_1, K_2, \ldots , K_n, K_{n+1}$ wpisanych w ustalony okrąg $O$ . Zauważmy, że nie istnieje punkt należący równocześnie do brzegów trzech spośród rozważanych kwadratów. Boki tych kwadratów mają bowiem jednakowe długości i są cięciwami danego okręgu. A przez żaden punkt wewnątrz okręgu (różny od jego środka) nie przechodzą oczywiście trzy cięciwy jednakowej długości.

Na łuku okręgu $O$ łączącym dwa kolejne wierzchołki $A$ i $B$ kwadratu $K_{n+1}$ leży dokładnie jeden wierzchołek kwadratu $K_j$ dla $1 \leq j \leq n$ . Wobec tego dowolny bok $\overline{AB}$ kwadratu $K_{n+1}$ przecina brzeg kwadratu $K_j$ w dwóch punktach, a brzeg kwadratu $K_{n+1}$ przecina brzeg kwadratu $K_j$ w ośmiu punktach. Z początkowej uwagi wynika, że dla $j = 1, 2, \ldots, n$ otrzymujemy w przecięciu brzegu kwadratu $K_j$ z brzegiem kwadratu $K_{n+1}$ zbiory ośmiopunktowe parami rozłączne. Zatem na brzegu kwadratu $K_{n+1}$ mamy $8n$ punktów należących do sumy brzegów kwadratów $K_1, K_2, \ldots, K_n$ . Punkty te wyznaczają $8n$ spójnych figur na brzegu kwadratu $K_{n+1}$ będących odcinkami lub sumami odcinków o wspólnym końcu. Każda z tych figur dzieli na dwie części jedną z części płaszczyzny otrzymanych po narysowaniu kwadratów $K_1, K_2, \ldots, K_n$ . Mamy więc zależność $a_{n+1} = a_n + 8n$ . Stąd wobec $a_1 = 2$ przez łatwą indukcję wynika, podobnie jak poprzednio, że dla dowolnej liczby naturalnej $k$ i $k$ kwadratów wpisanych w ustalony okrąg zachodzi wzór

$ a_k = 2 + 8 \cdot 1 + 8 \cdot 2 + \ldots + 8 \cdot (k-1) = (2k-1)^2+1. $

Dowiedliśmy więc, że największa liczba części, na które mogą rozciąć płaszczyznę brzegi $n$ kwadratów jest równa $(2n - 1)^2 + 1$ .

Uwaga 1. W podanym rozwiązaniu nie korzystaliśmy w sposób istotny z założenia, że rozważane figury są kwadratami. Gdyby były one prostokątami lub nawet dowolnymi czworokątami wypukłymi, to rozumowanie przebiegałoby tak samo. Zatem największa liczba części, na które mogą rozciąć płaszczyznę brzegi $n$ czworokątów wypukłych, jest równa $(2n - 1)^2 + 1$ . Natomiast dla czworokątów wklęsłych ta liczba jest większa.

Uwaga 2. Można analogicznie udowodnić, że największa liczba części, na które mogą rozciąć płaszczyznę brzegi $n$ trójkątów, jest równa $3n^2 - 3n + 2$ . Przeprowadzenie szczegółowego dowodu pozostawiamy czytelnikowi jako ćwiczenie.