Zadanie: V štvorci je zakreslených bodov. Dokážte, že existuje trojuholník s obsahom , ktorý obsahuje aspoň tri z týchto bodov. Body môžu byť aj na obvode trojuholníka.

meno: e-mail:

[cituj]lVu1bEPyV49 napísal: Lev: Zde1 sa, že s tfdm konvexnfdm oboalm me1š pravdu; je to origine1lny ne1pad, aj keď naprogramovanie by bolo pomerne zdĺhave9.Peter, komente1r 1: Veľmi ne1paditfd df4kaz, že to disjunkte9 pe1rovanie existuje. Dal by sa na tom založiť aj algoritmus ne1jdenia take9ho pe1rovania, ale bol by asi pomerne neefektedvny, aspoň teda v porovnaned s infdmi možnosťami.Peter, komente1r 2: Toto napadlo aj mňa, len by som dodal, že asi stačed dane9 body usporiadať a potom spojiť body, ktore9 sfa v tomto usporiadaned prvfd s druhfdm, treted so štvrtfdm a tak ďalej. Toto me1 zložitosť O(n.log(n)). Inak lepšia asymptoticke1 zložitosť sa nede1 dosiahnuť, pretože proble9m usporiadania n-tice čedsiel sa de1 previesť na tento proble9m, čiže ak by toto disjunktne9 pe1rovanie bolo možne9 urobiť s lepšou asymptotickou zložitosťou, potom by sme vedeli skonštruovať aj algoritmus na usporiadanie s ostro lepšou zložitosťou ako n.log(n), čo je mysledm doke1zane9, že je nemožne9.Peter, komente1r 3: Toto je ope4ť zaujedmavfd ne1pad, ale musel by som si ho trochu lepšie premyslieť, aby som sa k nemu mohol viac vyjadriť.Peter, komente1r 4: Presne toto bol mf4j pf4vodnfd argument, že disjunktne9 pe1rovanie existuje. Skre1tka pe1rovanie s minime1lnym sfačtom dĺžok spe1jajfacich fasečiek mused byť disjunktne9. však asi nie je optime1lna jednak preto, že jej zložitosť je pomerne vysoke1 a tiež preto, lebo na jej použitie už musedme mať vopred delenie bodov na dve skupiny a takfdch delened (a to aj špecie1lneho typu pol na pol) je veľmi veľa.[/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.