cięciwy w okręgu
cięciwy w okręgu
Witam! Mam do rozwiązania pewne zadanie. Otóż z podanej ilości punktów na okęgu mam wyliczyc na ile częsci [pól] zostanie on podzielony, gdy z punktów poprowadzimy cięciwy na zasadzie każdy - z każdym. Narazie udało mi się wybrowadzić wzór na ilosc cięciw : \(\displaystyle{ \frac{n ^{2} - n}{2}}\) . Czy istnieje jakiś wzór na ilosć takowych pól? Proszę o pomoc. Z góry dziękuję
-
Anathemed
- Użytkownik
- Posty: 101
- Rejestracja: 12 lip 2007, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 34 razy
cięciwy w okręgu
Tak, istnieje. Ilość pól dla n punktów = \(\displaystyle{ 2^{n-1}}\)
Jak ten wzór udowodnić? Indukcyjnie - trzeba sobie wyobrazić, ile nowych pól się tworzy po dołożeniu n+1 punktu na okręgu, gdy mamy już na nim n punktów.
Jak ten wzór udowodnić? Indukcyjnie - trzeba sobie wyobrazić, ile nowych pól się tworzy po dołożeniu n+1 punktu na okręgu, gdy mamy już na nim n punktów.
cięciwy w okręgu
Dzięki zią!
[ Dodano: 1 Października 2008, 21:59 ]
Czy aby napewno? Bo dla 6 puntów mamy 31 pól.:/
[ Dodano: 1 Października 2008, 21:59 ]
Czy aby napewno? Bo dla 6 puntów mamy 31 pól.:/
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
cięciwy w okręgu
Dodatkowym założeniem do zadania powinien być taki wybór punktów, że żadne trzy cięciwy nie przecinają się w jednym punkcie (inaczej zadanie nie będzie jednoznaczne).
I istotnie wzór będzie bardziej skomplikowany. Stosowna rekurencja to:
\(\displaystyle{ \begin{cases}
a_2=2 \\
a_{n+1}=a_n+n+ \sum_{k=0}^{n-1} k(n-k-1) \end{cases}}\)
Bierze się to mniej więcej stąd, że jak już mamy \(\displaystyle{ n}\) punktów i \(\displaystyle{ a_n}\) obszarów, to teraz dorysowujemy kolejny punkt i łączymy go kolejno z tamtymi. Ile będzie nowych obszarów? Każda nowa przekątna wyznacza nam tyle nowych obszarów z iloma starymi przekątnymi się przetnie plus jeden. "Plus-jedynki" dadzą nam w sumie \(\displaystyle{ n}\), natomiast jeśli patrzymy na przekątną łączącą nowy punkt ze starym, który jest na \(\displaystyle{ (k+1)}\)-szym miejscu licząc zgodnie ze wskazówkami zegara, to przetnie nam ona \(\displaystyle{ k(n-1-k)}\) starych przekątnych, bo po "prawej stronie" mamy \(\displaystyle{ k}\) punktów, a po "lewej" - \(\displaystyle{ (n-1-k)}\).
Tyle interpretacja kombinatoryczna, pozostaje rozwiązać tę rekurencję - ja zrobiłem to przy użyciu funkcji tworzących, ale można prościej, korzystając z faktu, że \(\displaystyle{ \sum_{k=0}^{n-1} k(n-k-1)= {n \choose 3}}\) (ten fakt odkryłem dopiero na końcu ;>). Odpowiedzią będzie:
\(\displaystyle{ a_n=1 + {n \choose 2} + {n \choose 4}}\)
(przyjmujemy, że \(\displaystyle{ {n \choose k}=0}\) dla \(\displaystyle{ n}\)
I istotnie wzór będzie bardziej skomplikowany. Stosowna rekurencja to:
\(\displaystyle{ \begin{cases}
a_2=2 \\
a_{n+1}=a_n+n+ \sum_{k=0}^{n-1} k(n-k-1) \end{cases}}\)
Bierze się to mniej więcej stąd, że jak już mamy \(\displaystyle{ n}\) punktów i \(\displaystyle{ a_n}\) obszarów, to teraz dorysowujemy kolejny punkt i łączymy go kolejno z tamtymi. Ile będzie nowych obszarów? Każda nowa przekątna wyznacza nam tyle nowych obszarów z iloma starymi przekątnymi się przetnie plus jeden. "Plus-jedynki" dadzą nam w sumie \(\displaystyle{ n}\), natomiast jeśli patrzymy na przekątną łączącą nowy punkt ze starym, który jest na \(\displaystyle{ (k+1)}\)-szym miejscu licząc zgodnie ze wskazówkami zegara, to przetnie nam ona \(\displaystyle{ k(n-1-k)}\) starych przekątnych, bo po "prawej stronie" mamy \(\displaystyle{ k}\) punktów, a po "lewej" - \(\displaystyle{ (n-1-k)}\).
Tyle interpretacja kombinatoryczna, pozostaje rozwiązać tę rekurencję - ja zrobiłem to przy użyciu funkcji tworzących, ale można prościej, korzystając z faktu, że \(\displaystyle{ \sum_{k=0}^{n-1} k(n-k-1)= {n \choose 3}}\) (ten fakt odkryłem dopiero na końcu ;>). Odpowiedzią będzie:
\(\displaystyle{ a_n=1 + {n \choose 2} + {n \choose 4}}\)
(przyjmujemy, że \(\displaystyle{ {n \choose k}=0}\) dla \(\displaystyle{ n}\)