Zadanie z matematyki dyskretnej - trójkąty z cięciw okręgu.

Question

Dzień dobry Państwu. Jeśli ktoś chciałby się pobaiwć, i jeśli komuś wyszłaby ta zabawa skutecznie, to proszę o niewielką podpowiedź do poniższego zadania:

Mamy n punktów na okręgu i prowadzimy wszystkie cięciwy łączące te punkty. Żadne 3 z nich nie przecinają się w 1 punkcie. Ile powstanie trójkątów wyznaczonych przez te cięciwy (liczymy wszystkie trójkąty, np. dla n=4 jest 8).

Próbowałem liczyć osobno trójkąty gdzie dwoma bokami są boki n-kąta (czyli "zewnętrzne cięciwy"), gdzie 1 bokiem jest bok n-kąta oraz gdzie żadnym z boków nie jest bok n-kąta. O ile pierwsze dwie grupy łatwo idzie, o tyle trzeciej nie idzie wyliczyć - cięciwy mają różne liczby przecięć, a trzeba brać takie trzy, żeby się przecinały lub miały wspólne wierzchołki (po jednym)....

Próbowałem też inaczej ale jakoś mi nie idzie to zadanie.

Powodzenia i dobrej zabawy, ja też będę nadal myślał i jeśli wymyślę to zamknę temat i napiszę odpowiedź.

Answer 1

DISCLAIMER

To co tutaj pokazuję to raczej szkic rozwiązania niż całe rozwiązanie.

OZNACZENIA

n, k - naturalne nieujemne

f(n, k) = n!/((n-k)!k!) gdy n >= k

f(n, k) = 0 gdy n < k

SZKIC ROZWIĄZANIA

Przez n tutaj oznaczam liczbę wierzchołków na okręgu.

Jak sobie popatrzysz na dowolny trójkąt to każdy jego wierzchołek leży na końcu cięciwy lub na przecięciu dwóch cięciw, zatem mamy 4 przypatki:

1. Dokładnie 3 wierzchołki leżą na końcach cięciw, takich trójkątów jest f(n, 3).
2. Dokładnie 2 wierzchołki leżą na końcach cięciw, takich trójkątów jest 4f(n, 4).
3. Dokładnie 1 wierzchołki leżą na końcach cięciw, takich trójkątów jest 5f(n, 5).
4. Dokładnie 0 wierzchołki leżą na końcach cięciw, takich trójkątów jest f(n, 6).

1) Jest dosyć prosty więc go pominę.

2) Niech ABC to trójkąt posiadający dokładnie 2 wierzchołki leżące na okręgu. Bez straty ogólności niech B, C to te punkty leżące na okręgu. Jak się popatrzy na przedłużenia odcinków AB oraz AC to one wyznaczają 2 punkty E, F na okręgu (różne od A oraz C). Jak się teraz popatrzymy na punkty E, F, B, C to one leżą na okręgu i istnieją 4 konfiguracje tych punktów wyznaczające różne trójkąty(*) z kategorii drugiej. Można poprowadzić rozumowanie odwrotne dla każdej 4-ki punktów na okręgu, przez co wszystkich trójkątów z kategorii drugiej jest 4 * f(n, 4).

(*) Na przykład FCEB, FCBE, BEFC, EBFC.

// Edit 1

łatwiej to zrozumieć jak widać to na rysunku, oznaczenia są takie same jak wyżej.

3, 4) Analogicznie do przypadku drugiego. Różnica jest taka że w 3) istnieje 5 różnych trójkątów powstałych z pięciu punktów oraz w 4) istnieje 1 różny trójkąt powstałych z sześciu punktów.

Łącznie więc mamy f(n, 3) + 4f(n, 4) + 5f(n, 5) + f(n, 6)

Warto zaznaczyć, że to rozumowanie pomija przypadki gdy więcej niż dwie cięciwy przecinają się w jednym punkcie, ale w założeniach zadania wykluczamy takie przypadki więc jest dobrze.

 

// Edit 2

Polecam encyklopedię ciągów: https://oeis.org/A006600.

Jak zadanie polega na wyznaczenie liczby czegoś od jakiejś innej liczby jak w tym przypadku to zawsze można policzyć klika wyrazów na palcach i spróbować znaleźć ten ciąg w encyklopedii ciągów. Czasem podają jakieś ciekawe źródła dotyczące danego ciągu.

Comments

Nie rozumiem dlaczego w ostatniej grupie możemy wziąć f(n,6). Przecież niektóre trójki cięciw się w ogóle nie przetną, i nie utworzą trójkąta....

---

f(n, 6) wybiera nam 6 punktów, a nie 3 cięciwy. Te 6 punktów tworzy nam 15 różnych cięciw przez co mamy f(15, 3) różnych konfiguracji trójek cięciw. Ja tylko twierdze że istnieje tylko jedna konfiguracja spośród tych f(15, 3) konfiguracji która tworzy trójkąt pasujący do kategorii 4-tej.

Oczywiście nie wszystkie te konfigurację mają sens, np jak oznaczy się te 6 punktów zgodnie z kierunkiem wskazówek zegara: A, B, C, D, E, F to można od razu wyrzucić cięciwy AB, BC, CD, DE, EF, FA ponieważ jak znajdują się w konfiguracji to łatwo pokazać że tylko co najwyżej 2 będą się przecinać, a chcemy aby 3 się przecinały. Przez co zostaje tylko do przeanalizowania f(9, 3) = 84 przypadki.

// Edit

Ładny argument redukujący wszystkie przypadki do jednego.

Aby cięciwa przecinała się z dwiema innymi cięciwami na tych 6 punktach to musi mieć 2 punkty po obu stronach bo w innym przypadku będzie mała mniej niż 2 przecięcia z innymi cięciwami na tych 6 punktach więc jedyna cięciwa której jednym z końców jest A to AD (to już można na placach policzyć 5 przypadków). Analogicznie dla B to BE oraz dla C to CF.

Stosując oznaczenia co wyżej tylko AD, BE, CF tworzą konfigurację która daje nam trójkąt z kategorii 4-tej.

---

Ok, teraz rozumiem. Dziękuję za pomoc.

 

Pozdrawiam!