Rozdělení kruhu na oblasti - Dividing a circle into areas

Počet body (n), akordy (C) a regiony (r_G) pro prvních 6 termínů problému Moserova kruhu

v geometrie, problém rozdělení kruhu na oblasti prostřednictvím zapsaného polygon s n strany takovým způsobem, aby maximalizovat počet oblastí vytvořených hranami a úhlopříčky, někdy nazývané Moserův kruhový problém, má řešení indukční metodou. Největší možný počet regionů, r_G = ( ⁿ
₄ ) + ( ⁿ
₂ ) + 1, což dává sekvenci 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, ... (OEIS: A000127). Ačkoli prvních pět podmínek odpovídá geometrický průběh 2^{n − 1}, rozchází se n = 6, ukazující riziko generalizace pouze z několika pozorování.

Lemma

Pokud existují n přidají se body na kruhu a přidá se ještě jeden bod, n čáry lze kreslit z nového bodu do dříve existujících bodů. Jsou možné dva případy. V prvním případě (A), nová čára prochází bodem, kde se protínají dvě nebo více starých čar (mezi dříve existujícími body). Ve druhém případě (b), nová čára protíná každou ze starých čar v jiném bodě. Bude užitečné znát následující skutečnost.

Lemma. Nový bod A lze zvolit tak, že případ b dojde pro každý z nových řádků.

Důkaz. Pro případ A, tři body musí být na jednom řádku: nový bod A, starý bod Ó ke kterému je nakreslena čára, a bod Já kde se protínají dvě staré čáry. Existují n staré body Ó, a tedy konečně mnoho bodů Já kde se protínají dvě staré čáry. Pro každého Ó a Já, linie OI prochází kružnicí v jiném bodě než Ó. Protože kružnice má nekonečně mnoho bodů, má bod A který nebude na žádném z řádků OI. Pak pro tento bod A a všechny staré body Ó, případ b bude pravda.

Toto lemma znamená, že pokud existují k křížení linií AO, pak každý z nich kříží AO v jiném bodě a k + 1 linka vytvoří nové oblasti AO.

Řešení

Induktivní metoda

Lema vytváří důležitou vlastnost pro řešení problému. Zaměstnáním induktivní důkaz, lze dospět k vzorci pro F(n) ve smyslu F(n − 1).

Na obrázku tmavé čáry spojují body 1 až 4 rozdělující kruh na 8 celkových oblastí (tj. F(4) = 8). Tento obrázek ilustruje indukční krok od n = 4 až n = 5 s přerušovanými čarami. Když se přidá pátý bod (tj. Při výpočtu F(5) pomocí F(4)), výsledkem budou čtyři nové řádky (přerušované čáry v diagramu), které jsou přidány, očíslované 1 až 4, jedna pro každý bod, ke kterému se připojují. Počet nových regionů zavedených pátým bodem lze tedy určit na základě počtu regionů přidaných každou ze 4 linek. Soubor i spočítat přidávané řádky. Každá nová čára může překonat řadu stávajících čar, v závislosti na tom, ke kterému bodu jde (hodnota i). Nové řádky se nikdy nepřekročí, kromě nového bodu.

Počet řádků, které protíná každá nová čára, lze určit na základě počtu bodů na „levé“ čáře a počtu bodů na „pravé“ čáře. Vzhledem k tomu, že všechny existující body již mají mezi sebou čáry, je počet bodů vlevo vynásobený počtem bodů vpravo počet řádků, které budou překračovat novou čáru. Pro přímku k bodu i, existují

n − i − 1

body vlevo a

i - 1 bod

vpravo celkem celkem

(n − i − 1) (i − 1)

čáry musí být překročeny.

V tomto příkladu řádky do i = 1 a i = 4 každý protíná nulové čáry, zatímco řádky do i = 2 a i = 3 každý překračuje dvě čáry (na jedné straně jsou dva body a jeden na druhé straně).

Opakování lze tedy vyjádřit jako

${ Displaystyle f (n) = f (n-1) + součet _ {i = 1} ^ {n-1} levý (1+ levý (ni-1 pravý) levý (i-1 dobře dobře)}$

které lze snadno snížit na

${ displaystyle f (n) = f (n-1) + součet _ {i = 1} ^ {n-1} vlevo (2-n + ni-i ^ {2} vpravo)}$

pomocí součtu prvního ${ displaystyle (n-1)}$ přirozená čísla a první ${ displaystyle (n-1)}$ čtverce, to se spojí

${ displaystyle f (n) = f (n-1) + { frac {1} {6}} n ^ {3} -n ^ {2} + { frac {17} {6}} n-2 }$

Konečně

${ displaystyle f (n) = součet _ {k = 1} ^ {n} vlevo ({ frac {1} {6}} k ^ {3} -k ^ {2} + { frac {17 } {6}} k-2 vpravo) +1}$ s ${ displaystyle f (0) = 1}$

který přináší

${ displaystyle f (n) = { frac {n} {24}} (n ^ {3} -6n ^ {2} + 23n-18) +1}$

Metoda kombinatoriky a topologie

Lema tvrdí, že počet oblastí je maximální, pokud jsou všechny „vnitřní“ průniky akordů jednoduché (přesně dva akordy procházejí každým průsečíkem uvnitř). Bude tomu tak v případě, že budou vybrány body v kruhu “v obecné poloze ". Za tohoto předpokladu„ generické křižovatky “lze počet oblastí určit také neinduktivním způsobem pomocí vzorce pro Eulerova charakteristika a připojeno rovinný graf (zobrazeno zde jako graf vložený dokoule S ²).

Rovinný graf určuje a buněčný rozklad letadla s F tváře (2-rozměrné buňky), E hrany (1-rozměrné buňky) a PROTI vrcholy (0-rozměrné buňky). Když je graf připojen, Eulerův vztah pro 2-dimenzionální sféru S ²

${ displaystyle , V-E + F = 2}$

drží. Zobrazte diagram (kruh společně se všemi akordy) výše jako rovinný graf. Pokud obecné vzorce pro PROTI a E lze nalézt oba, vzorec pro F lze také odvodit, což problém vyřeší.

Jeho vrcholy zahrnují n body na kruhu, označované jako vnější vrcholy, stejně jako vnitřní vrcholy, průsečíky odlišných akordů ve vnitřku kruhu. Výše uvedený předpoklad „generické křižovatky“ zaručuje, že každý vnitřní vrchol je průsečíkem ne více než dvou akordů.

Proto je hlavním úkolem při určování PROTI zjišťuje počet vnitřních vrcholů. V důsledku lemmatu jakékoli dva protínající se akordy jednoznačně určí vnitřní vrchol. Tyto akordy jsou zase jednoznačně určeny čtyřmi odpovídajícími koncovými body akordů, kterými jsou všechny vnější vrcholy. Jakékoli čtyři vnější vrcholy určují a cyklický čtyřúhelník a všechny cyklické čtyřstěny jsou konvexní čtyřúhelníky, takže každá sada čtyř vnějších vrcholů má přesně jeden průsečík tvořený jejich úhlopříčkami (akordy). Dále podle definice Všechno vnitřní vrcholy jsou tvořeny protínajícími se akordy.

Proto je každý vnitřní vrchol jednoznačně určen kombinací čtyř vnějších vrcholů, kde je počet vnitřních vrcholů dán vztahem

${ displaystyle V _ { text {interiér}} = {n vyberte 4},}$

a tak

${ displaystyle V = V _ { text {exteriér}} + V _ { text {interiér}} = n + {n vyberte 4}.}$

Okraje zahrnují n kruhové oblouky spojující páry sousedních vnějších vrcholů, stejně jako segmenty akordické čáry (popsané níže) vytvořené uvnitř kruhu sbírkou akordů. Jelikož existují dvě skupiny vrcholů: vnější a vnitřní, lze segmenty chordální čáry dále rozdělit do tří skupin:

1. Hrany přímo (neřezané jinými akordy) spojující dva vnější vrcholy. Jedná se o akordy mezi sousedními vnějšími vrcholy a tvoří obvod mnohoúhelníku. Existují n takové hrany.
2. Hrany spojující dva vnitřní vrcholy.
3. Hrany spojující vnitřní a vnější vrchol.

Chcete-li zjistit počet hran ve skupinách 2 a 3, zvažte každý vnitřní vrchol, který je spojen s přesně čtyřmi hranami. To přináší

${ displaystyle 4 {n vyberte 4}}$

hrany. Protože každá hrana je definována dvěma vrcholy koncových bodů, byly vyčísleny pouze vnitřní vrcholy, hrany skupiny 2 se počítají dvakrát, zatímco hrany skupiny 3 se počítají pouze jednou.

Každý akord, který je řezán jiným (tj. Akordy, které nejsou ve skupině 1), musí obsahovat dvě hrany skupiny 3, jeho počáteční a koncový akordický segment. Jelikož akordy jsou jednoznačně určeny dvěma vnějšími vrcholy, existují celkem

${ displaystyle 2 left ({n vyberte 2} -n right)}$

skupina 3 hrany. To je dvojnásobek celkového počtu akordů, které samy nejsou členy skupiny 1.

Součet těchto výsledků dělený dvěma dává kombinovaný počet hran ve skupinách 2 a 3. Přidání n hrany ze skupiny 1 a n kruhové obloukové hrany přináší součet

${ displaystyle E = { frac {4 {n zvolit 4} +2 doleva ({n zvolit 2} -n doprava)} {2}} + n + n = 2 {n zvolit 4} + {n vyberte 2} + n.}$

Střídání PROTI a E do Eulerova vztahu vyřešeného pro F, ${ displaystyle , F = E-V + 2,}$ jeden pak získá

${ displaystyle F = {n vyberte 4} + {n zvolte 2} +2.}$

Jelikož jedna z těchto ploch je zevnějšek kruhu, počet oblastí r_G uvnitř kruhu je F - 1 nebo

${ displaystyle r_ {G} = {n vyberte 4} + {n vyberte 2} +1,}$

který řeší na

${ displaystyle r_ {G} = { frac {n!} {(n-4)! 4!}} + { frac {n!} {(n-2)! 2!}} + 1}$

který poskytuje stejný kvartický polynom získaný pomocí indukční metody

${ displaystyle r_ {G} = { frac {1} {24}} n (n ^ {3} -6n ^ {2} + 23n-18) +1}$

Viz také

• Sekvence líného kuchaře - kde n je počet přímých řezů

Reference

• Conway, J. H. a Guy, R. K. „Kolik regionů?“ v Kniha čísel. New York: Springer-Verlag, s. 76–79, 1996.
• Weisstein, Eric W. „Circle Division by Chords“. MathWorld.
• http://www.arbelos.co.uk/Papers/Chords-regions.pdf