Matematické Fórum

petrnovak123 · 08. 11. 2016 16:15

Ve městě Kocourkově zřídili tři komise: sportovní, kulturní a zkrášlovací. V komisích smějí zasedat pouze radní anebo starosta. Pan starosta prohlásil, že nepřichází v úvahu, aby se stal členem zkrášlovací komise, poněvadž je sám o sobě dost velkou okrasou města. Kvůli sporům o podobě sochy na městské kašně nesmějí mít kulturní a zkrášlovací komise žádné společné členy. Určete, kolika způsoby lze komise obsadit, bylo-li do slovutné rady města zvoleno kromě pana starosty ještě dalších sedm ctihodných radních. Nezapomeňte započíst případy, kdy se do některé nebo ani do žádné komise nikdo nepřihlásí.

Došel jsem k tomu, že sportovní komisi můžeme obsadit 2^8 způsoby (neboli $\sum_{k=0}^8{8 \choose k}$ ), stejně tak kulturní. Zkrášlovací 2^7 způsoby.
2^8 + 2^8 + 2^7 = 640

A tady jsem skončil, protože nevím, jak zohlednit tu podmínku, že zkrášlovací a kulturní komise nesmí mít společné členy. Nejspíš to povede na využití PIE, ale opravdu mě nenapadá, jak ho tam zakomponovat.

Za každou, byť sebemenší radu, budu moc vděčný.

Stýv · 08. 11. 2016 17:09

řekl bych, že je třeba odečíst ty případy, kde mají Z a K komise společného alespoň jednoho člena. ale pak musíš vrátit ty případy, kde mají společné dva členy, protože jsi je odečetl dvakrát... už tam vidíš využití PIE?

petrnovak123 · 08. 11. 2016 17:41

Princip mi je jasný, nicméně stále nevím, jak to převést do řeči kombinačních čísel. Snažil jsem se na netu najít řešené příklady podobného typu, bohužel jsem žádné nenašel.
Abych se dopracoval k výsledku, musel bych si vypsat všechny možné možnosti a pak je sečíst, což je děsně nepraktický.

Stýv · 08. 11. 2016 19:18

1) teď jsem si uvědomil, že to tvoje sčítání možností není správně, má se násobit 2^8*2^8*2^7
2) např. s alespoň 1 společným členem: 7 možností, jak vybrat toho společného (starosta to být nemůže) * 2^7 zbývající členové K *2^6 zbývající členové Z * 2^7 členové S
3) napadlo mě, že se to dá celý zjednodušit bez použití PIE. každý radní může mít jednu N kombinací funkcí: K, Z, S, K+Z, K+S, ..., takže pak je 7^N kombinací pro radní *(N-1) za starostu

petrnovak123 · 08. 11. 2016 19:27

Taky jsem to původně násobil, ale pak jsem si řekl, že ty jednotlivé komise jsou nezávislé a nijak spolu nesouvisí, neviděl jsem tak důvod k násobení. Asi bych nad tím příště neměl tak přemýšlet a hledat chyby tam, kde nejsou :D

Každopádně díky za ten bod 2), hned je mi to jasnější, ještě se nad tím zamyslím a snad to dám nějak dohromady :)

Matematické Fórum

#1 08. 11. 2016 16:15

Princip inkluze a exkluze

#2 08. 11. 2016 17:09

Re: Princip inkluze a exkluze

#3 08. 11. 2016 17:41

Re: Princip inkluze a exkluze

#4 08. 11. 2016 19:18

Re: Princip inkluze a exkluze

#5 08. 11. 2016 19:27

Re: Princip inkluze a exkluze

Zápatí