Zadanie: Na obrázku je nakreslených priamok tak, že žiadne dve z nich nie sú rovnobežné, žiadne dve nie sú na seba kolmé a žiadne tri neprechádzajú jedným bodom. Najviac koľko ostrouhlých trojuholníkov (v závislosti od ) môže byť na obrázku?

meno: e-mail:

[cituj]Feráč napísal: Aby vám nebolo ľúto, že nie sú vzoráky, tak tu máte aspoň veľmi stručné návody/riešenia. Každej priamke vieme jednoznačne priradiť uhol z intervalu $[0, 180^\circ)$, ktorý zviera s x-ovou osou. Tri priamky s uhlami $\alpha < \beta < \gamma$ teraz tvoria ostrouhlý trojuholník práve vtedy, keď $$\beta - \alpha < 90^\circ, \gamma - \beta < 90^\circ, \gamma - \alpha > 90^\circ.$$ Úlohu si môžeme preformululovať: potrebujeme rozmiestniť $2n+1$ bodov do intervalu $[0,180^\circ)$ tak, aby tam bolo čo najviac takýchto trojíc $\alpha, \beta, \gamma$. Každá taká trojica má $\alpha < 90^\circ$ a $\gamma \geq 90^\circ$. Kde môže byť $\beta$? Buď $\beta < 90^\circ$ a potom už stačí aby $\gamma-\beta < 90^\circ$ (prvý prípad), alebo $\beta \geq 90^\circ$ a potom už stačí aby $\beta-\alpha < 90^\circ$ (druhý prípad). Teraz trik. Nakreslime si všetky tieto body len do intervalu $[0, 90^\circ)$ nasledovne. Body, ktoré sú $< 90^\circ$ necháme na mieste a dáme im bielu (B) farbu. Body, ktoré sú $\geq 90^\circ$ zmenšíme o $90^\circ$ ("posunieme doľava") a nakreslíme ich čiernou (Č) farbou. Žiadne dve priamky nie sú na seba kolmé, takže žiadne dva body takto nepadnú na to isté miesto. Dobré trojice $\alpha, \beta, \gamma$ teraz presne zodpovedajú postupnostiam BČB (prvý prípad) a ČBČ (druhý prípad). Znovu si môžeme úlohu preformulovať: potrebujeme ofarbiť $2n+1$ guľôčok čiernou a bielou farbou, aby sme dosiahli čo najviac trojíc BČB a ČBČ (nie nutne susedných gúľočok). Toto je už čisto kombinatorická úloha. Dokážte si, že najlepšie je dať čierne a biele na striedačku. Potom to vyjde $n(n+1)(2n+1)/6$, presne tak ako vraví Mišof :)[/cituj]

V príspevku je na písanie matematických výrazov možné používať príkazy TeXu. Help k ich používaniu nájdete na kms.sk/tex.php.