Koło które dzieli płaszczyznę

[Ruahyin]

Koło dzieli płaszczyznę na dwa obszary; można ją podzielić dwoma kołami na
cztery, potem dorysować trzecie koło tak, aby powstała figura ośmioobszarowa.
Czy istnieje układ czterech kół dzielący płaszczyznę na 16 obszarów?

[jutrvy]

Nie.

[Slup]

Nie będę tak lakoniczny jak jutrvy.

Niech będą dane trzy okręgi \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\).
Założymy dodatkowo, że \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\) dzielą płaszczyznę na co najwyżej \(\displaystyle{ 8}\) obszarów.
Przyjmijmy, że dodaliśmy jeden okrąg \(\displaystyle{ O}\). Załóżmy, że poruszamy się po okręgu \(\displaystyle{ O}\) zgodnie z ruchem wskazówek zegara zaczynając z pewnego punktu. W trakcie naszego ruchu będziemy kolejno odwiedzali obszary \(\displaystyle{ U_1}\), \(\displaystyle{ U_2}\),..., \(\displaystyle{ U_n}\) i \(\displaystyle{ U_{n+1}=U_1}\) wyznaczone przez okręgi \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\). Ciąg
\(\displaystyle{ U_1}\), \(\displaystyle{ U_2}\),..., \(\displaystyle{ U_n}\)
nie musi składać się z różnych obszarów, ale to nie jest poważny problem. Łatwo zauważyć, że okręgi \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\), \(\displaystyle{ O}\) dzielą płaszczyznę na co najwyżej \(\displaystyle{ 8+n}\)-obszarów. Przy czym sam okrąg \(\displaystyle{ O}\) dodaje \(\displaystyle{ n}\) obszarów do tych wykreślonych przez \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\). Jeżeli
\(\displaystyle{ 8+n\geq 16}\)
to \(\displaystyle{ n\geq 8}\). Przy przejściu z jednego obszaru do drugiego znajdujemy się w punkcie przecięcia okręgu \(\displaystyle{ O}\) z jednym z okręgów \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\). To oznacza, że okrąg \(\displaystyle{ O}\) ma z trzema okręgami \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\) aż \(\displaystyle{ 8}\) punktów przecięcia. Każde dwa okręgi mają co najwyżej dwa punkty przecięcia. Powinniśmy zatem dostać co najwyżej \(\displaystyle{ 2\cdot 3=6}\) punktów przecięcia. Otrzymaliśmy sprzeczność. Tym samym uzasadniliśmy odpowiedź jutrvy-ego z dokładnością do zdania:

Okręgi \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\), \(\displaystyle{ O_3}\) dzielą płaszczyznę na co najwyżej \(\displaystyle{ 8}\) obszarów.

[dec1]

Ogólnie, za pomocą \(\displaystyle{ n}\) kół płaszczyznę można podzielić maksymalnie na \(\displaystyle{ n^2-n+2}\) części.

[Slup]

Dec1 to bardzo ciekawy fakt. Dziękuję.
Załóżmy, że mamy \(\displaystyle{ n}\)-okręgów \(\displaystyle{ O_1}\),...,\(\displaystyle{ O_n}\), które dzielą płaszczyznę na co najwyżej \(\displaystyle{ n^2-n+2}\) obszarów. Dodajemy jeden okrąg \(\displaystyle{ O}\). Obchodzimy \(\displaystyle{ O}\) zgodnie z ruchem zegara i bierzemy ciąg \(\displaystyle{ U_1}\),...,\(\displaystyle{ U_k}\) obszarów już wykreślonych przez \(\displaystyle{ O_1}\),...,\(\displaystyle{ O_n}\), które kolejno odwiedzamy. Oczywiście \(\displaystyle{ U_{k+1}=U_1}\). Znowu w ciągu
\(\displaystyle{ U_1}\),...,\(\displaystyle{ U_k}\)
pewne wyrazy mogą się powtarzać, ale to nie jest problem. Uzyskujemy, że okręgi \(\displaystyle{ O}\), \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\),...,\(\displaystyle{ O_n}\) dzielą płaszczyznę na co najwyżej \(\displaystyle{ n^2-n+2+k}\) obszarów.
Dwa okręgi mogą się przecinać w co najwyżej dwóch punktach. Zatem liczba punktów przecięcia okręgu \(\displaystyle{ O}\) ze wszystkimi okręgami \(\displaystyle{ O_1}\),...,\(\displaystyle{ O_n}\) wynosi co najwyżej \(\displaystyle{ 2n}\). Przy przejściu z \(\displaystyle{ U_i}\) do \(\displaystyle{ U_{i+1}}\) musimy przejść przez punkt przecięcia \(\displaystyle{ O}\) z jednym z okręgów \(\displaystyle{ O_1}\),...,\(\displaystyle{ O_n}\). Zatem dostajemy, że
\(\displaystyle{ k\leq 2n}\)
Stąd liczba obszarów wykreślonych przez okręgi \(\displaystyle{ O}\), \(\displaystyle{ O_1}\), \(\displaystyle{ O_2}\),...,\(\displaystyle{ O_n}\) wynosi co najwyżej
\(\displaystyle{ n^2-n+2+k\leq n^2-n+2+2n=(n+1)^2-(n+1)+2}\)

Z zasady indukcji matematycznej dostajemy, że \(\displaystyle{ n}\) okręgów wykreśla na płaszczyźnie co najwyżej \(\displaystyle{ n^2-n+2}\) obszarów.

Ale to się da zrealizować?

[jutrvy]

Można napisać równanie rekurencyjne na maksymalną liczbę obszarów wyznaczonych przez \(\displaystyle{ n}\) okręgów. Jeśli tę liczbę oznaczymy przez \(\displaystyle{ f(n)}\), to wówczas mamy następujące związki:

\(\displaystyle{ f(1) = 2}\)
\(\displaystyle{ f(n) = f(n-1) + n + 1}\).

Dlaczego? Potrafisz to pokazać? Można łatwo znaleźć odpowiednią konfigurację kół (coś w rodzaju pawiego oczka, tylko takiego z przecięciami), które spełniają te równania. Że lepiej się nie da, już pokazałeś, pozostaje tylko rozwiązać rekurencję

[Slup]

Można napisać równanie rekurencyjne na maksymalną liczbę obszarów wyznaczonych przez \(\displaystyle{ n}\) okręgów. Jeśli tę liczbę oznaczymy przez \(\displaystyle{ f(n)}\), to wówczas mamy następujące związki:

\(\displaystyle{ f(1) = 2}\)
\(\displaystyle{ f(n) = f(n-1) + n + 1}\).

Dlaczego? Potrafisz to pokazać? Można łatwo znaleźć odpowiednią konfigurację kół (coś w rodzaju pawiego oczka, tylko takiego z przecięciami), które spełniają te równania. Że lepiej się nie da, już pokazałeś, pozostaje tylko rozwiązać rekurencję

Potrafię świetnie pokazywać nieprawdziwe twierdzenia, ale zazwyczaj robię to łatwiej. Tym razem się powstrzymam, chociaż pokusa jest silna . Rozumiem, że Twoim zdaniem:
\(\displaystyle{ f(2)=f(1)+2+1=2+2+1=5}\)

Poprawna wersja to
\(\displaystyle{ f(n+1)=f(n)+2n}\)
i faktycznie nierówność
\(\displaystyle{ f(n+1)\leq f(n)+2n}\)
wynika z mojego wpisu. Tylko nie rozumiem po co ta rekurencja i czemu twierdzisz, że wystarczy ją rozwiązać. Przecież jej rozwiązanie podał już Dec1 i jest nim \(\displaystyle{ n^2-n+2}\), a zatem znałem to rozwiązanie już wcześniej. Podobnie znałem samą rekurencję(może nie aż tak explicite, ale przynajmniej w poprawnej formie). Jak sam widzisz z teorio-informacyjnej analizy większości Twojego wpisu wynika, że niesie on \(\displaystyle{ 0}\)-bitów informacji. Jeżeli uwzględnić błędną rekurencje, to chyba należałoby przyjąć, że ta informacja jest ujemna.
Jedyny interesujący, ale niejasny fragment Twojego wpisu, dotyczy tego pawiego oczka. Zostaw lepiej te niepotrzebne rekurencje w spokoju i uzasadnij, że można narysować to pawie oczko z poprzesuwanymi \(\displaystyle{ n}\) okręgami, gdzie \(\displaystyle{ n\in \mathbb{N}}\). Będę naprawdę wdzięczny!

[jutrvy]

Tak, rOMBnąłem się :p jest późno...-- 6 gru 2016, o 00:29 --Nie umiem tu rysować.