Podział płaszczyzny przez n połączonych punktów

[PokeKolekcjoner]

Witam, proszę o pomoc/wskazówkę w rozwiązaniu podanego zadania:

Obierzmy n punktów dowolnie położonych na płaszczyźnie, przyjmując założenie że żadne trzy z nich nie są współliniowe. Wyznacz maksymalną liczbę podziałów płaszczyzny powstałych po połączeniu tych punktów każdy z każdym.

Tutaj jeszcze dodam drobne wyjaśnienie o jakich podziałach jest mowa. Dla trzech punktów mamy trójkąt i dwa podziały płaszczyzny(wnętrze i zewnętrze trójkąta). Dla czterech mamy kwadrat z obiema przekątnymi, wewnątrz są 4 podziały na zewnątrz 1 - w sumie 5. Próbowałem doszukiwać się jakiegoś wzoru rekurencyjnego, niestety bez skutku. Z góry dziękuję za pomoc.

[arek1357]

Dla trzech punktów mamy trójkąt i dwa podziały płaszczyzny(wnętrze i zewnętrze trójkąta). Dla czterech mamy kwadrat z obiema przekątnymi, wewnątrz są 4 podziały na zewnątrz 1 - w sumie 5.

To nie jest prawda... dla trzech masz już 7 podziałów

Dodano po 24 minutach 57 sekundach:
Poza tym może się zdarzyć, że punkty nie współliniowe (trzy) wyznaczać ci będą obszary, gdzie mogą pojawić się np. proste równoległe i wtedy ilość obszarów się zmniejszy...

Dodano po 6 minutach 1 sekundzie:
Sensowne jest szukanie górnej granicy

Wzór na ilość obszarów, które dzielą płaszczyznę k prostych jest:

\(\displaystyle{ \frac{k^2+k+2}{2} }\)

Ale Ty masz \(\displaystyle{ n}\) punktów, które wyznaczają:

\(\displaystyle{ k= {n \choose 2}}\) - prostych

Więc górna granica powinna być:

\(\displaystyle{ \frac{ {n \choose 2}^2+ {n \choose 2}+2 }{2} }\)

Zawsze przy prostych równoległych ilość obszarów spada diametralnie...

[PokeKolekcjoner]

Przepraszam za niedoprecyzowanie treści zadania ale rozważamy połączenie n punktów przez odcinki, a nie przez proste. Stąd też pewnie wychodzi Ci 7 dla trzech punktów. Szukamy górnej granicy.

//EDIT: Mam podejrzenie, że dla odcinków będzie największa liczba podziałów jeśli żadne trzy z nich nie przetną się w jednym punkcie.

[arek1357]

Oczywiście robiłem dla prostych...

Dodano po 2 godzinach 7 minutach 11 sekundach:
Więc ja bym to zadanie sformułował tak:

Na ile obszarów maksymalnie dzielą przekątne wielokąta wypukłego (obszar poza wielokątem zawsze można dodać w formie jedynki)

I zauważ, że jeżeli wielokąt będzie foremny to nie osiągniemy maksymalnej ilości obszarów dla \(\displaystyle{ n>5}\)

Więc jak zauważyłem ( z obserwacji) , ładnie to zaczyna wychodzić:

\(\displaystyle{ n=2 \rightarrow 1}\)

\(\displaystyle{ n=3 \rightarrow 1}\)

\(\displaystyle{ n=4 \rightarrow 4 \cdot 1=4}\)

\(\displaystyle{ n=5 \rightarrow 5+5 \cdot 1+1=11}\)

\(\displaystyle{ n=6 \rightarrow 6+6 \cdot 2+6 \cdot 1+1=25}\)

\(\displaystyle{ n=7 \rightarrow 7+7 \cdot 3+7 \cdot 2+7 \cdot 1+1=50}\)

\(\displaystyle{ n=8 \rightarrow 8+8 \cdot 4+8 \cdot 3+8 \cdot 2+8 \cdot 1+1=89}\)

................................................................................................

itd...

Teraz można łatwo wyprodukować ładny wzór...

Dodano po 29 minutach 27 sekundach:
lub prościej:

\(\displaystyle{ 4 \cdot 1=4}\)

\(\displaystyle{ 5 \cdot 2+1=11}\)

\(\displaystyle{ 6 \cdot 4+1=25}\)

\(\displaystyle{ 7 \cdot 7+1=50}\)

\(\displaystyle{ 8 \cdot 11+1=89}\)

.........................

itd...

Z tego produkujemy ładny wzór:

\(\displaystyle{ a_{n}=\left( n+3\right) \cdot \frac{n^2-n+2}{2}+1 }\)

Lub:

\(\displaystyle{ a_{1}=4}\)

\(\displaystyle{ a_{n}= \frac{n^3+2n^2-n+8}{2} , n \ge 2 }\)

gdzie:

\(\displaystyle{ a_{n}}\) - maksymalna ilość obszarów wyprodukowanych przez boki i przekątne \(\displaystyle{ n+3}\) - wielokąta wypukłego...