Trójkąty w trójkącie

[mol_ksiazkowy]

Wewnątrz trójkąta jest skończona liczba punktów, które są łączone ze sobą i z wierzchołkami trójkąta odcinkami tak aby żadne z tych odcinków się nie przecinały i żeby cały trójkąt był podzielony na mniejsze trójkąciki. Udowodnić, że liczba tych trójkącików jest nieparzysta.

[arek1357]

Jest to jak na mój gust zwykła triangulacja trójkąta...

I jak pojedziemy indukcyjnie dla \(\displaystyle{ n=1,2}\) zachodzi , łatwo zauważyć(n- ilość punktów w trójkącie)

Zachodzi dla pewnego n

to n+1 wszy punkt musi się znaleźć w którymś z trójkątów (wnętrze) i teraz ten punkt możemy połączyć tylko z wierzchołkami trójkąta w którym ten punkt się znajduje, co zwiększy ilość trójkątów o dwa a, że poprzednia ilość była nieparzysta to zwiększenie o dwa da dalej liczbę nieparzystą...cnd...

[kerajs]

Możesz pokazać tę indukcję na poniższym przykładzie:

\(\displaystyle{ \begin{tikzpicture}

\draw (-1,3)--(-4,0)--(4,0)--(0,6)--(-4,0)--(0,1)--(4,0)--(1,3)--(0,1)--(-1,3)--(1,3)--(0,6)--(-1,3);
\fill[cyan] (-4,0) circle(0.1);
\fill[cyan] (4,0) circle(0.1);
\fill[cyan] (0,1) circle(0.1);
\fill[cyan] (0,6) circle(0.1);
\fill[cyan] (-1,3) circle(0.1);
\fill[cyan] (1,3) circle(0.1);
\end{tikzpicture}}\)

[a4karo]

Jeszcze trzeba rozważyć przypadek gdy nowy punkt wypadnie na istniejącej krawędzi

[arek1357]

przypadek Kejrasa tak jak opisałem wcześniej punkt wpada do trójkąta dowolnego i mamy o dwa więcej czyli w tym przypadku 9(dziewięć).

Przypadku punktów leżących na linii nie rozpatrywałem, ale można taki punkt zamknąć w najmniejszym
czworokącie i też wyjdzie liczba nieparzysta trójkątów bo dojdzie cztery trójkąty zawarte w tym czworokącie co da tę samą nieparzystą liczbę.

[Dudenzz]

\(\displaystyle{ \begin{tikzpicture} \draw (-3,0)--(0,3)--(3,0)--(-3,0)--(0,1.5)--(3,0)--(0,1.5)--(0,3)--(3,0)--(1,1)--(0,3)--(1,1)--(-3,0);
\fill[cyan] (-3,0) circle(0.1); \fill[cyan] (3,0) circle(0.1); \fill[cyan] (0,3) circle(0.1); \fill[cyan] (0,1.5) circle(0.1); \fill[red] (1,1) circle(0.1); \end{tikzpicture}}\)

Czyli tak, i zamiast dwóch trókątów (w czworokącie) mamy cztery (w tym samym czworokącie).

Co do przedstawionego wcześniej przykładu - chyba nie chodzi o to, żeby pokazać jak będzie wyglądał krok kolejny, tylko o to, że według indukcji, którą proponujesz dla zadanej listy wierzchołków istnieje jedno rozwiązanie. Tymczasem rozwiązań może być więcej niż liczba permutacji zbioru elementów takiej listy. Jednym z przykładów jest rozwiązanie zaproponowane przez kerajsa.

[Slup]

Niech \(\displaystyle{ T}\) to będzie ten trójkąt. Niech \(\displaystyle{ K}\) będzie liczbą odcinków i \(\displaystyle{ S}\) będzie liczbą trójkącików w tym podziale. Jeżeli uwzględnimy duży trójkąt \(\displaystyle{ T}\), to wszystkich trójkątów jest \(\displaystyle{ S+1}\). Każdy odcinek jest wspólnym bokiem dokładnie dwóch trójkątów spośród tych \(\displaystyle{ S+1}\) trójkątów. Stąd \(\displaystyle{ 2K = 3(S+1)}\), a więc \(\displaystyle{ S+1}\) jest liczbą parzystą. Czyli \(\displaystyle{ S}\) jest liczbą nieparzystą.

[arek1357]

Czyli tak, i zamiast dwóch trókątów (w czworokącie) mamy cztery (w tym samym czworokącie).

Właśnie o tym mówiłem a jeżeli chodzi o jakieś permutacje to nie ma potrzeby zawracać nimi głowy...
Nie chodziło mi w żaden sposób o liczbę możliwości bo to nie istotne było...

[kerajs]

@ arek1357,
Zarówno mój poprzedni post, jak i odpowiedzi a4karo i Dudenzza miały Ci pokazać, że rozwiązanie które podałeś dotyczy tylko niektórych podziałów trójkąta.

Przypuszczam że odmiennie rozumiemy treść zadania. Moim zdaniem chodziło o wykazanie tezy przy dowolnie podzielonym trójkącie (także takich podziałach jak na powyższych grafikach, a których nie uzyskasz ze swojej 'indukcji') , a Ty (jak sądzę) przyjmujesz że samodzielnie dokonujesz tego podziału.

refleksja:    

Podobnego uproszczenia (co szybko wyłapał i adekwatnie skomentował Swistak) dokonałem w zadaniu 2. w 423787.htm , jednak tam posty pisałem wyłącznie dla facecji (choć pewnie tylko dla mnie było to śmieszne (gdyż jedną z moich licznych wad jest wypaczone poczucie humoru)).

PS
Sądzę, że nie ma sensu poprawiać tej 'indukcji' skoro Slup zamieścił błyskotliwie proste rozwiązanie.

[arek1357]

Zarówno mój poprzedni post, jak i odpowiedzi a4karo i Dudenzza miały Ci pokazać, że rozwiązanie które podałeś dotyczy tylko niektórych podziałów trójkąta.

A czy są jeszcze inne podziały trójkąta jak na trójkąty , i przypadek graniczny gdy punkt wpada na bok jakiegoś podziałowego trójkąta?

[a4karo]

arek1357, sprawdź, że podziału z obrazku kerajsa nie dostaniesz w procedurze indukcyjnej. Zatem dowód indukcyjny nie obejmuje wszystkich przypadków.