Afiliacja: Politechnika Śląska
Miesiąc temu przyglądaliśmy się pewnym własnościom podziału płaszczyzny na sześciokąty. Tym razem również będziemy dzielić płaszczyznę, lecz skupimy się na maksymalnej liczbie części, jaką można w ten sposób otrzymać. Dwa klasyczne przykłady w tej tematyce dotyczą prostych i okręgów.
Na ile (najwięcej) obszarów może podzielić płaszczyznę \(n\) prostych?
Rys. 1
Liczba obszarów jest maksymalna tylko wtedy, gdy proste znajdują się w położeniu ogólnym (żadne dwie nie są równoległe ani żadne trzy nie przecinają się w jednym punkcie). Załóżmy bowiem, że do \((n-1)\) prostych na płaszczyźnie dokładamy kolejną. Jeżeli proste są w położeniu ogólnym, to nowa prosta ma z pozostałymi dokładnie \((n-1)\) punktów przecięcia – więc jest dzielona na \(n\) części (dwie półproste i \((n-2)\) odcinków). Zatem po dołączeniu do podziału \(n\)-tej prostej liczba obszarów zwiększyła się dokładnie o \(n.\) W ten sposób wykazujemy, że maksymalna liczba obszarów otrzymanych przy użyciu \(n\) prostych to: \[R_p(n)=\frac12(n^2+n+2).\] Początkowe wyrazu ciągu \(R_p(n)\) to \(2,\,4,\,7,\,11\) i \(16.\)
Zastanówmy się teraz nad kolejnym pytaniem:
Na ile (najwięcej) obszarów może podzielić płaszczyznę \(n\) okręgów?
Jeden okrąg dzieli płaszczyznę na dwie części. Gdy w odpowiedni sposób dorysujemy drugi, liczba obszarów zwiększy się o \(2.\) Po odpowiednim dorysowaniu trzeciego okręgu zwiększymy liczbę obszarów o \(4,\) a po narysowaniu czwartego – o \(6.\) Ogólnie, optymalnie ułożonych \(n\) okręgów daje liczbę obszarów o \(2(n-1)\) większą niż optymalnie ułożonych \((n-1)\) okręgów. Dlaczego tak jest? Zachęcam do samodzielnego zastanowienia się nad tym pytaniem.
Rys. 2
W każdym razie z powyższej obserwacji wynika, że maksymalna liczba obszarów otrzymanych przy użyciu \(n>0\) okręgów to: \[R_o(n)=n^2-n+2,\] a początkowe wyrazy ciągu \(R_o(n)\) to \(2,\,4,\,8,\,14\) i \(22.\)
Powyższe dwa zadania należą do klasyki kombinatoryki i często służą dydaktycznie jako jedne z pierwszych przykładów przy wprowadzaniu pojęcia rekurencji.
Rys. 3
Połączmy teraz świat okręgów ze światem (pół)prostych: Lizakiem nazywamy zbiór punktów będący sumą okręgu i półprostej o początku w środku okręgu, z wyłączeniem promienia okręgu należącego do tej półprostej (patrz rys. 3). Dodajmy, że promień został usunięty z lizaka, zapewne ze względów bezpieczeństwa, aby nie ukłuć się nim podczas ewentualnej konsumpcji. Pod koniec 2025 roku Neil Sloane zadał następujące pytanie:
Rys. 4
Na ile (najwięcej) obszarów może podzielić płaszczyznę \(n\) lizaków?
Zauważmy, że dwa lizaki mogą się przeciąć w co najwyżej siedmiu punktach (patrz rys. 4 ) – i daje to optymalne \(10\) obszarów. Przy odpowiednim ułożeniu trzech lizaków otrzymujemy największą możliwą liczbę regionów równą \(25.\) Jak wygląda ogólny wzór ciągu? Zapewne jest dość skomplikowany, ale Cutler, Karlsson i Sloane otrzymali ładne oszacowanie górne: \[R_l(n)\leqslant\frac12(7n^2-5n+2),\] które niestety nie jest optymalne: ci sami autorzy wykazali, że poprawną odpowiedzią już dla czterech lizaków jest \(45,\) a nie \(47.\) Zapewne lada dzień rozstrzygnie się, czy maksymalna liczba obszarów, którą da się uzyskać, mając do dyspozycji pięć lizaków, to \(70\) czy \(71.\) A co z sześcioma lizakami? Nie wiadomo.
David O. H. Cutler, Jonas Karlsson, Neil J. A. Sloane, Cutting a Pancake with an Exotic Knife (2025). Sloane na swojej stronie internetowej opublikował również króciutki artykulik The Lollipop Problem.