Domovská stránka Jiřího Kalvody

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

Připomeňme, že graf G je (vrcholově) 2-souvislý, právě když ho lze vyrobit z kružnice pomocí operací přidávání ucha.

  1. Nechť GG je graf s aspoň třemi vrcholy. Dokažte, že GG je 2-souvislý, právě když pro každé tři různé vrcholy x,y,zx, y, z existuje v GG cesta z xx do yy obsahující zz.
  2. Nechť GG je graf s aspoň třemi vrcholy. Dokažte, že GG je 2-souvislý, právě když pro každé tři různé vrcholy x,y,zx, y, z existuje v GG cesta z xx do yy neobsahující zz.

Počítání dvěma způsoby

  1. Na vysoké škole si každý student zapsal aspoň 10%10\% ze všech nabízených předmětů. Dokažte, že existuje předmět, na němž je zapsáno aspoň 10%10\% všech studentů.
  2. Z přednášky víme, že na vrcholech {1,2,,n}\{1, 2, \dots , n\} existuje nn2n^{n-2} stromů. Kolik z nich obsahuje hranu {1,2}\{1, 2\}?
  3. Na turnaji v trojkovém mariáši (což je hra pro tři hráče) bylo 3232 účastníků, 1212 z nich sehrálo pět partií, 2020 z nich sehrálo šest partií. Kolik tam bylo sehráno partií?
  4. Na jiném turnaji v trojkovém mariáši bylo 1515 úč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áč?
  5. Turistický oddíl má 100100 členů. Pro své členy oddíl zorganizoval celkem 1010 výletů. Na každém výletě bylo nejvýše 3030 členů oddílu. Dokažte, že existují dva členové oddílu, kteří spolu nikdy nebyli na společném výletě.
  6. Nechť MM je matice tvaru 10×1010\times 10 obsahující čísla 1,2,,101, 2, \dots , 10, přičemž každé číslo se v ní vyskytuje 1010-krát. Dokažte, že MM má řádek nebo sloupec obsahující aspoň 4 různá čísla. Jak zobecnit tento závěr na matice tvaru n×nn\times n, v nichž se každé z čísel 1,2,,n1, 2, \dots , n vyskytuje právě nn-krát?