Matematické Fórum

andulkas · 28. 02. 2017 18:22

Ahojda.

Mám tady takový příklad.

Zadání:
Na přímce je dáno 50 úseček. Dokažte, že platí aspoň jedno z následujících tvrzení:
a) existuje 8 úseček se společným bodem
b) existuje 8 úseček, z nichž každé dvě jsou disjuntkní

Když si to nějak vhodně zvolím, tak dostanu som úseček se společným bodem. Obecně ale áčko platit nebude, ne?

Takže musím dokázat, že pokud nenastane a), pak nastane b), jelikož dokazuji platnost aspoň jednoho z těch tvrzení.

Ale jak na to?
Děkuji za úvodní rady.

check_drummer · 28. 02. 2017 21:23

Ahoj,
podle těch čísel co tam vidím by mohlo platit obecné tvrzení - místo 50 volit $n^2+1$ a místo 8 volit n+1. Tj. výše uvedený příklad je speciálním případem pro n=7.

check_drummer · 28. 02. 2017 21:48

Možná to půjde nějak elegantněji, ale předpokládejme sporem, že to tvrzení neplatí, tj. ani a) ani b) nenastane.

Sestrojím maximální množinu disjunktních úseček (asi nebude těžké dokázat, že to je ona): Hladovým algoritmem vyberu takovou úsečku s nejmenším pravým okrajem (která je diskunktní s doposud vybranými), tyto úsečky označím ui. Tedy díky tomu že b) neplatí je úseček ui nejvýše n.

Každý pravý okraj každé ui může "pokrývat" nejvýše n-1 dalších úseček (jinak by platilo a)) - to máme tedy celkem nejvýše $n^2$ úseček. A asi nebude těžké dokázat, že žádné další úsečky neexistují - tj. každá úsečka je buď jedna z ui a nebo pokrývá pravý okraj nějaké ui. Ale to, že máme jen nejvýše $n^2$ úseček je spor s předpokladem, že úseček je alespoň $n^2+1$ .

Úvaha výše platí pro "uzavřené" úsečky (s krajními body), asi bude možné ji upravit i pro "otevřené" nebo "polootevřené" úsečky.

andulkas · 04. 03. 2017 18:05

Jasne asi chápem, jak se dělá důkaz když neplatí a) a dokáže se, že patí b). Mimochodem dokazuje se nějak když neplatí b) pak musí nastat a).

check_drummer · 07. 03. 2017 18:48

↑ andulkas:
Ahoj, ale já jsem z toho, že neplatí ani a) ani b) odvodil spor.

Matematické Fórum

#1 28. 02. 2017 18:22

kombinatorická geometrie

#2 28. 02. 2017 21:23

Re: kombinatorická geometrie

#3 28. 02. 2017 21:48

Re: kombinatorická geometrie

#4 04. 03. 2017 18:05

Re: kombinatorická geometrie

#5 07. 03. 2017 18:48

Re: kombinatorická geometrie

Zápatí