Matematické Fórum

↑ surovec: Zajímavý vzorec. Smím se zeptat na postup, jak na něj přijít? Na oplátku pak nabídnu svůj. :-)

↑ surovec: jj, tohle zní legit. Otázka, jestli by to nějak elegantně šlo sečíst, aniž bys tu sumu musel štěpit na podpřípady a ty pak dělat separátně.

Já na to šel takto - rozdělil jsem si trojúhelníky na 3 kategorie:
i) různostranné ... počet různých typů označím [mathjax]x[/mathjax]
ii) rovnoramenné (ale ne rovnostranné) ... počet různých typů označím [mathjax]y[/mathjax]
iii) rovnostranné ... ten je buď jednoho typu (pokud N je dělitelné číslem 3), nebo žádný neexistuje. Označme počet typů jako [mathjax]z[/mathjax], kde [mathjax]z \in \{ 0, 1 \}[/mathjax].

Je tedy zjevné, že počet všech typů trojúhelníků bude [mathjax]P(N) = x+y+z[/mathjax]. Nyní stačí tyto čísla určit.

Půjdu na to trochu oklikou - budu si teď všímat i různých poloh. Ke každému typu trojúhelníku může existovat více různých poloh (viz zadání). Uvažme, že máme nějaký konkrétní 1 typ trojúhelníku a chceme určit počet poloh. Ten závisí na tom, zda ten typ trojúhelníku je různostranný (i), rovnoramenný (ii), nebo rovnostranný (iii).

i) Nejdřív umístím nejkratší stranu trojúhelníku. Tomu mohu udělat N způsoby. Následně si vyberu polohu vrcholu naproti nejdelší straně. To mohu udělat dvěma způsoby. Takže celkem ke každému typu různostranného trojúhelníku budu mít 2N různých poloh.
ii) U každého typu rovnoramenného trojúhelníku stačí umístit vrchol mezi dvěma rameny (to jde udělat N způsoby), pak je již poloha trojúhelníku určena jednoznačně.
iii) U rovnostranného trojúhelníku budu mít jen [mathjax]\frac{N}{3}[/mathjax] navzájem různých poloh (například rotací o 120° nic nového nezískám)

Pokud tedy zohledňuju i polohy, tak všech možných trojúhelníků ve všech možných polohách bude:
[mathjax]x \cdot 2N + y\cdot N + z \cdot \frac{N}{3}[/mathjax]

Já ale tento počet umím určit i jiným způsobem - mohu prostě zvolit libovolnou trojici vrcholů v původním [mathjax]N[/mathjax]-úhelníku (na jejich pořadí nezáleží), což lze provést [mathjax]N \choose 3[/mathjax] způsoby. Musí tedy platit:

[mathjax]{N \choose 3} = x \cdot 2N + y\cdot N + z \cdot \frac{N}{3} [/mathjax]

Počet typů různostranných trojúhelníků [mathjax]x[/mathjax] se určuje špatně. Ale počet rovnostranných trojúhelníků [mathjax]z[/mathjax] je buď 0, nebo 1 (viz poznámka výše). No a co počet všech rovnoramenných trojúhelníků [mathjax]y[/mathjax] ? To taky půjde:

Uvažme kružnici opsanou N-úhelníku - vrcholy N-úhelníku zde vymezují stejně dlouhé obloučky. Chceme zvolit délku ramena trojúhelníku (to je zde vlastně jediný stupeň volnosti). Co o ramenu víme? Rameno propojuje vrcholy vzdálené nejméně 1 oblouček a nejvýše (ale ne přímo rovno) [mathjax]\frac{N}{2}[/mathjax] obloučků. Takže délku ramena mohu zvolit [mathjax]\left \lfloor {\frac{N-1}{2}} \right \rfloor [/mathjax] způsoby. Musím si však dát pozor - nesmím započítat rovnostranný trojúhelník (pokud by se objevil). Takže jako opravu ještě odečtu [mathjax]z[/mathjax]:
[mathjax]y = \left \lfloor {\frac{N-1}{2}} \right \rfloor - z[/mathjax]

Po dosazení do rovnice výše:
[mathjax]{N \choose 3} = x \cdot 2N + \Big( \left \lfloor {\frac{N-1}{2}} \right \rfloor - z \Big) \cdot N + z \cdot \frac{N}{3}[/mathjax]

Odtud vyjádříme [mathjax]x[/mathjax]:
[mathjax]x = \frac{(N-1)(N-2)}{12} - \frac{1}{2} \left \lfloor \frac{N-1}{2}\right  \rfloor + \frac{z}{3}[/mathjax]

Celkový počet různých typů trojúhelníků je (viz úvaha výše) roven [mathjax]P(N) = x + y+ z[/mathjax]. Po dosazení:

[mathjax]P(N) = \frac{(N-1)(N-2)}{12} + \frac{1}{2} \left \lfloor \frac{N-1}{2}\right  \rfloor + \frac{z}{3}[/mathjax]

Připomínám, že [mathjax]z = 1[/mathjax] pro [mathjax]N[/mathjax] dělitelné třemi, [mathjax]z=0[/mathjax] v opačném případě.

Tím je úloha vyřešená.

↑ surovec:
Ahoj asi by bylo možné vyjádřit tu sumu pomocí uzavřeného tvaru, jen to bude trochu pracnější (rozlišit případy modulo 6, apod.), ale v podstatě jde o součet aritmetické posloupnosti.

Pozdravujem,
Napada ma aj takato varianta cvicenia z #1.
Kolko roznych trojuholnikov moze vpisananych do N-uholnika, ak aj dva isometricke trojuholniky, ktore sa nedaju stotoznit posunutiami a ani otoceniami a ani ich kombinaciami nepovazujeme  za totozne. 
Napr v pravidelnom 6-uholniku ABCDEF,  trojuholniky ABD a ABE su take nestotozitelne.

↑ surovec:

Ještě jsem zkoušel, zda se nedá vymeyslet nějaký obecný postup: Označme hledaný počet p(n) (ve tvaru té sumy). Zkoumejme diference mezi p(n+1) a p(n), tato diference vychází celkem pěkně:

Mezi 6k a 6k+1: k
Mezi 6k+1 a 6k+2: k
Mezi 6k+2 a 6k+3: k+1
Mezi 6k+3 a 6k+4: k
Mezi 6k+4 a 6k+5: k+1
Mezi 6k+5 a 6(k+1): k+1

teď jde jen o to z toho vytvořit nějaký vzorec. Samozřejmě můžu tvrdit, že se dá z těch diferencí ten Anonymystikův vzorec vykoukat a pak dokázat indukcí, ale možná půjde něco lepšího.

Možná bude existovat i obecný postup, kdy diference je polynom v proměnné k a místo 6k+i budu mít obecně mk+i.

(A diference těch diferencí vypadá ještě více pěkně: 0,1,-1,1,0,0.)

Ahoj ↑ check_drummer:,
Zda sa mi, ze pocet hladanych rieseni v #1 je prirozdzene cislo najlblizsie k nejakemu vyrazu, tak ako prirozdzene cislo najlblizsie k [mathjax]\frac {(N+3)^2}{12}[/mathjax],  je pocet prirodzenych  rieseni (nuloych alebo kladnych) diofanttickej rovnice [mathjax]a+2b+3c=N[/mathjax] .

Edit.  No mozno je to blba konjonktura.

↑ check_drummer: Já teď začal kvůli tomu problému studovat Pólyovu enumerační teorii, abych tento druh problémů uměl řešit obecněji. Například kdybych trojúhelník nevpisoval do pravidelného mnohoúhelníku, ale třeba na obvod čtvercové mřížky (a pouze do mřížových bodů), nebo do vrcholů nějakého Platónského tělesa, apod. Jiné zobecnění by mohlo být, kdybychom nevpisovali trojúhelníky, ale obecně M-úhelníky.
--
Uvědomil jsem si, že tento druh problémů souvisí se symetriemi, k jejichž popisu se používá teorie grup. No tak jsem to začal studovat, prokousal jsem se až k Burnsidovu lemmatu, ale to v daném kontextu nejde jednoduše použít, tak musím šáhnout ještě k tomuhle:
https://en.wikipedia.org/wiki/P%C3%B3ly … on_theorem
--
Je to docela zajímavé čtení.
--
Jinak ten problém s N-úhelníkem mi přinesla přítelkyně, že ho řešili ve škole, tak jsem to s ní začal řešit a uvědomil jsem si, že je to netriviální a že by se to možná hodilo i sem (jen abyste věděli story, kde se úloha vzala :-D ).

Ahoj ↑ check_drummer:,
To si robil to overenie z #16, informatickou cestou?
Dokaz citovaneho vysledku v #13 je napr. v knihe od Polya, Szegö: Problems and theorem in Analysis l .

Este som pozeral aj https://oeis.org/search?q=+0%2C0%2C1%2C … ;go=Search , mozno aj to je zaujimave si blizsie pozriet.

Ahoj ↑ check_drummer:,
Akoze sa moja intuicia z #13 potvrdila, ( dakujem ti za overenie toho) tak mozno by sa mohla prehlbit analogicka metoda.  Mozno  clanok od E.Fogels z 1941 moze  dat myslienky (tyka sa celych bodoch blizkych danej rovnnej krivky).
Mozno aj ty najdes nejaku literaturu o tom.