#1 26. 11. 2015 11:48
Kombinace s pootočením
Dobrý den,
řeším následující úlohu a vůbec nevím, jak začít:
K jednání u kulatého stolu se sešlo 47 obrů a 47 skřítků. Kolika různými způsoby se můžou posadit, když rozesazení, která se liší jen pootočením, považujeme za identická? (Obři jsou všichni stejní, stejně tak skřítkové. Může se hodit dokázat následující tvrzení: je-li kolem stolu n pozic, a rozesazení R se pootočením o k pozic (1≤k<n) nezmění, pak se R nezmění ani pootočením o d pozic, kde d je nějaký dělitel n menší než n.)
Napadá někoho něco? Díky...
Offline
#3 28. 11. 2015 15:55
- check_drummer
- Příspěvky: 5575
- Reputace: 106
Re: Kombinace s pootočením
↑ 5tudentka:
Ahoj, máme štěstí, že 47 je prvočíslo. Já bych řekl, že se daná pozice (protože máme m:=2.47 židlí) může zopakovat po pootočení buď o 1 nebo o 2 nebo 47 nebo o 2.47 (to jsou rozklady m) - vezmeme nejmenší i takové, že po pootočení o i získáme stejnou pozici. Dle mého 1 a 47 nepřipadne v úvahu a tedy zbývá 2 a m - a 2 dle mého nastane jen pro případ, kdy se obři a trpaslící pravidelně střídají.
Možné je vhodné si to rozmyslet pro měnší prvočíslo než 47, např. 3 nebo 5.
"Máte úhel beta." "No to nemám."
Offline