Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 23. 10. 2021 18:00
Kombinatorika - zaujímavý príklad
Zdravím, prichádzam s prosbou o pomoc pri riešení tohto príkladu.
Zadanie znie:
Dvaja učitelia skúšajú súčasne skupinu 8 študentov, každý jeden predmet. Každý študent odpovedá z jedného predmetu 30 minút. Koľko existuje
rozvrhov skúšania, ak požadujeme, aby skúšky skončili za štyri hodiny?
Pokyny. Výsledok vyjadrite pomocou súčtovej notácie Σ.
Ako by ste v tomto príklade postupovali?
Offline
#2 23. 10. 2021 18:41
- check_drummer
- Příspěvky: 4623
- Reputace: 99
Re: Kombinatorika - zaujímavý príklad
Ahoj, není jasné, zda studenti musí každý vykonat zkoušku z obou předmětů, nebo z alespoň jednoho, nebo dokonce případně i z žádného...?
"Máte úhel beta." "No to nemám."
Offline
#3 23. 10. 2021 19:04
Re: Kombinatorika - zaujímavý príklad
↑ Vé:
Ahoj, kdyby musel bejt kazdej ze studentu zkousenej prave dvakrat - tj. u kazdeho ze zkousejicich prave jednou - tak by to znamenalo, ze pro kazdou permutaci studentu v rozvrhu u zkousejiciho c.1 jsou pripustne pouze ty permutace studentu v rozvrhu u zkousejiciho c.2, ktere maji na i-item miste jineho studenta, nez ma na i-tem miste zkousejici c.1, i=1,2,...,8, (student nemuze byt zkousen najednou u obou dvou). Jde tedy o to najit pocet permutaci bez pevneho bodu - k tomu by ti mohla pomoci napr. wiki.
Offline
#4 24. 10. 2021 21:07
Re: Kombinatorika - zaujímavý príklad
↑ Vé: Nejdřív bych umístil do rozvrhu prvního studenta: u prvního učitele mám 8 možností a u druhého sedm. Druhého studenta mohu umístit na zbylé pozice, tzn. 7 a 6 možností. Atd. Celkem tedy podle mě [mathjax2]8\cdot 7\cdot 7\cdot 6\cdot 6\cdot 5\cdot 5\cdot 4\cdot 4\cdot 3\cdot 3\cdot 2\cdot 2=8\cdot (7!)^2[/mathjax2]
Ale krk bych za to nedal...
Offline
#5 24. 10. 2021 21:48
Re: Kombinatorika - zaujímavý príklad
↑ surovec:
Ahoj, uz kdyz umistujes toho druheho studenta k druhemu uciteli, tak zalezi, kam jsi ho dal k prvnimu:
Pro moznost
ucitel 1: A X B X X X X X
ucitel 2: X A X X X X X X
mas doopravdy jen 6 moznosti, kam umistit studenta B k druhemu uciteli.
Ale pro moznost
ucitel 1: A B X X X X X X
ucitel 2: X A X X X X X X
mas tech moznosti 7. Takze tvuj vysledek bude nejspis mensi, nez spravna odpoved.
Offline
#6 24. 10. 2021 22:24
Re: Kombinatorika - zaujímavý príklad
↑ surovec:
S týmto modelom je jeden problém. Označme skúšajúcich A, B a nech A1 je prvý študent u skúšajúceho A, B1 prvý študent u skúšajúceho B atď. Potom
surovec napsal(a):
Nejdřív bych umístil do rozvrhu prvního studenta: u prvního učitele mám 8 možností a u druhého sedm. Druhého studenta mohu umístit na zbylé pozice, tzn. 7
potiaľto súhlas
surovec napsal(a):
... a 6 možností. Atd. ...
tu je spomínaný problém. Potrebujeme vedieť počet možností, ktoré máme pre pozíciu druhého študenta u druhého skúšajúceho (B2). Určite vtedy nemôže byť skúšaný rovnaký študent, ako je v tom čase u prvého skúšajúceho (A2), takže počet možností je najviac 7. Ale ak študent na pozícii A2 je rovnaký ako B1, tak na pozíciu B2 máme 7 kandidátov, nie 6. Napísať, že máme 6 možností predpokladá, že študenti A2 a B1 sú rôzni, ale taká požiadavka v zadaní nie je a celkovo znižuje počet možných rozvrhov.
surovec napsal(a):
Ale krk bych za to nedal...
Opatrnosti nie je nikdy dosť :)
↑ Vé:
U skúšajúceho A môže byť ľubovoľné poradie študentov, t.j. akákoľvek permutácia.
U skúšajúceho B musíme zabezpečiť, aby v danom čase uňho nemal naplánovanú skúšku študent, ktorý je v rovnakom čase u skúšajúceho A. Teda pre každú permutáciu študentov u skúšajúceho B musí platiť, že nemá pevný bod, t.j. nenecháva žiaden prvok na svojom mieste.
Zistiť počet permutácií bez pevného bodu je klasické použitie princípu zapojenia a vypojenia / inklúzie a exklúzie. Zrejme ste ho preberali, keďže zadanie vyslovene požaduje napísať výsledok v tvare sumy, takže len v stručnosti:
Od počtu všetkých permutácií odpočítaš počet tých, ktoré nechávajú aspoň 1 prvok na svojom mieste. Tým si však odpočítal príliš veľa, takže pripočítaš počet tých, ktoré nechávajú aspoň dva prvky na svojom mieste. Potom musíš pripočítať počet tých, ktoré nechávajú na svojom mieste aspoň 3 prvky atď. ... až po počet permutácií, ktoré enchávajú na mieste všetkých 8 prvkov. Tým získaš požadovaný tvar výsledku v súčtovom zápise.
Offline
#7 24. 10. 2021 22:31
Re: Kombinatorika - zaujímavý príklad
↑ surovec:
toto naozaj nie je OK. Spravna odpoved je na tej wiki co dal laszky.
Ucitel A vybera lubovolnu permutaciu a B vybera lubovolny "derangement", t.j. permutaciu, kde ziaden ziak nie je na "svojom mieste", kde "jeho miesto" je pozicia co vybral ucitel A, t.j.
[mathjax](8!)(!8)=(8!)^2\sum_{k=0}^8\frac{(-1)^k}{k!}[/mathjax]
Offline
#9 25. 10. 2021 11:30
- check_drummer
- Příspěvky: 4623
- Reputace: 99
Re: Kombinatorika - zaujímavý príklad
↑ Vé:
Ještě není jasné, zda učitel zkouší v daný okamžik právě jednoho studenta nebo může i víc. Např. dá jednomu otázku, ten se připravuje a zkouší druhého...
"Máte úhel beta." "No to nemám."
Offline