KG1 Jiří Kalvoda: Cvičení 11
Also available as: PDF Markdown
Informace k cvičení jsou na https://kam.mff.cuni.cz/~jirikalvoda/vyuka/24z/kg1.
Ušaté lemma
- Nechť je graf s aspoň třemi vrcholy. Dokažte, že je 2-souvislý, právě když pro každé tři různé vrcholy existuje v cesta z do obsahující .
- Nechť je graf s aspoň třemi vrcholy. Dokažte, že je 2-souvislý, právě když pro každé tři různé vrcholy existuje v cesta z do neobsahující .
Počítání dvěma způsoby
- Na vysoké škole si každý student zapsal aspoň ze všech nabízených předmětů. Dokažte, že existuje předmět, na němž je zapsáno aspoň všech studentů.
- Z přednášky víme, že na vrcholech existuje stromů. Kolik z nich obsahuje hranu ?
- Na turnaji v trojkovém mariáši (což je hra pro tři hráče) bylo účastníků, z nich sehrálo pět partií, z nich sehrálo šest partií. Kolik tam bylo sehráno partií?
- Na jiném turnaji v trojkovém mariáši bylo účastníků a každá dvojice účastníků se tam právě dvakrát sešla u společné partie. Kolik tam bylo sehráno partií? Plyne ze zadání, že každý hráč sehrál stejný počet partií? Pokud ano, kolik partií sehrál každý hráč?
- Turistický oddíl má členů. Pro své členy oddíl zorganizoval celkem výletů. Na každém výletě bylo nejvýše členů oddílu. Dokažte, že existují dva členové oddílu, kteří spolu nikdy nebyli na společném výletě.
- Nechť je matice tvaru obsahující čísla , přičemž každé číslo se v ní vyskytuje -krát. Dokažte, že má řádek nebo sloupec obsahující aspoň 4 různá čísla. Jak zobecnit tento závěr na matice tvaru , v nichž se každé z čísel vyskytuje právě -krát?