XXVIII - II - Zadanie 6

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

\[<br /> (1) \qquad a_{n+1} \leq a_n + 8n.<br /> \]

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

\[<br /> a_k < 2 + 8 \cdot 1 + 8 \cdot 2 + \ldots + 8 \cdot (k - 1),<br /> \]

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

\[<br /> 2 + 8(1+2 + \ldots + (k-1)) = 2 + 8 \cdot \frac{k(k-1)}{2} =<br /> 2 + 4k^2 - 4k = (2k - 1)^2 + 1,<br /> \]

czyli ostatecznie

\[<br /> (2) \qquad a_n \leq (2k-1)^2 + 1 \ \textrm{dla} \ k = 1,2,\ldots.<br /> \]

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

\[<br /> a_k = 2 + 8 \cdot 1 + 8 \cdot 2 + \ldots + 8 \cdot (k-1) = (2k-1)^2+1.<br /> \]

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź