Matematické Fórum

bsft · 17. 11. 2009 09:24 — Editoval bsft (17. 11. 2009 09:24)

Ahojte, nevím si rady s tímto příkladem, mohli byste mi ukázat jak na to?

Ve skupině n lidí zná každý nějakou "horkou novinku" (zvanou také "drb"), kterou nikdo ze zbývajících lidí nezná. Navzájem si drby sdělují telefonem, přičemž při každém telefonátu si oba účastníci poví navzájem všechny drby, které se dozvěděli. Pokud například jeden telefonující zná jen jednu (svoji) horkou novinku a druhý již zná tři jiné, tak po skončení telefonu znají oba všechny čtyři drby. Ukažte, že pro n ≥ 4 vždy stačí 2n-4 telefonátů, aby se každý z n lidí dozvěděl všechny drby.
Označení má býrt následující: nejmenší počet telefonů pro skupinu n lidí jako D(n). Určit D(1), D(2), D(3), D(4) a dále postupovat matematickou indukcí.

Olin · 17. 11. 2009 11:24

D(4) určíme snadno - zavolají si "do čtverce", nejprve protější strany, pak zbývající dvě, takže celkem 4 zavolání. Nyní chceme ukázat, že přidáním dalšího člověka se počet telefonátů zvedne nejvýše o dva. To uděláme tak, že nejprve ten nový zavolá komukoliv jinému, zbytek lidí si pak zavolá jako obvykle, přičemž drb toho nového se rozšíří zároveň s drbem toho, komu byl na začátku řečen. Až si tato stará parta všechno poví (což z indukčního předpokladu víme, že zvládnou pomocí 2n-4 hovorů), kdokoliv z nich zavolá tomu novému a řekne mu všechno. Tím pádem ví všichni všechno a počet hovorů narostl pouze o dva.

Matematické Fórum

#1 17. 11. 2009 09:24 — Editoval bsft (17. 11. 2009 09:24)

Kombinatorika + indukce

#2 17. 11. 2009 11:24

Re: Kombinatorika + indukce

Zápatí