Mam problem z następującym zadaniem:
\(\displaystyle{ \mathbb{N}=\left\{ 1,2,3,\ldots \right\}}\)
\(\displaystyle{ m,n,k,s \in \mathbb{N}}\)
Na konkursie tańca spotyka się \(\displaystyle{ m}\) panów i \(\displaystyle{ n}\) pań. Każdy pan z każdą panią ma zatańczyć \(\displaystyle{ k}\) różne tańce (tańcząc z daną panią dany taniec tylko raz). Jaka jest najmniejsza liczba grań orkiestry (orkiestra w danej chwili gra tylko do jednego tańca), jeżeli jednocześnie może tańczyć co najwyżej \(\displaystyle{ s}\) par?
\(\displaystyle{ f:\mathbb{N}^4 \rightarrow \mathbb{N} \cup \left\{ 0\right\} \\ f(m,n,k,s)=?}\)
\(\displaystyle{ f}\) - funkcja określająca najmniejszą liczbę grań orkiestry
Gdyby orkiestra grała dla każdej pary osobno, to musiałaby grać najmniej \(\displaystyle{ mnk}\) razy, ale nie wiem jak to powiązać z \(\displaystyle{ s}\). Nie mogę wymyślić wzoru na \(\displaystyle{ f(m,n,k,s)}\).
panie, panowie i tańce
-
rozprzedstud
- Użytkownik
- Posty: 76
- Rejestracja: 2 cze 2014, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 24 razy
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
panie, panowie i tańce
Wyda mi się, że trzeba najpierw ustalić kogo jest więcej pań czy panów, jeżeli więcej jest panów, to powinniśmy zrobić tak:
ponumerujmy sobie panów od \(\displaystyle{ 1..n}\) i pań od \(\displaystyle{ 1...m}\) i niech:
\(\displaystyle{ n \ge m}\) odrzućmy teraz od \(\displaystyle{ m+1...n}\) panów, którzy nie zatańczą bo nie mają pary,
Znajdzie się gotowych do tańca \(\displaystyle{ m}\) par i teraz jeszcze jedna rozkmina czy \(\displaystyle{ s \le m}\)
czy może: \(\displaystyle{ s > m}\) bo w takim razie pary te trzeba byłoby grupować po \(\displaystyle{ s}\)
plus reszta, która zostanie.
Na razie nie będę się tym bawił, założę roboczo, że wszystkie \(\displaystyle{ m}\) pary sobie na parkiecie tańczą i gra orkiestra.
I teraz ten sam taniec musi zatańczyć każda para spośród kobiet i panów na parkiecie partnerzy zmieniają się
\(\displaystyle{ m}\) razy
sposobów, potem znowu pozostałych panów ustawiam z paniami i dalej orkiestra nie zmienia nuty
zakładam, że: \(\displaystyle{ n=am+r}\)
czyli orkiestra nie zmienia nuty przez:
\(\displaystyle{ (a+1)m}\) tańców
a potem zaczyna się wszystko od początku bo idzie kolejny taniec.
To tak z grubsza...
ponumerujmy sobie panów od \(\displaystyle{ 1..n}\) i pań od \(\displaystyle{ 1...m}\) i niech:
\(\displaystyle{ n \ge m}\) odrzućmy teraz od \(\displaystyle{ m+1...n}\) panów, którzy nie zatańczą bo nie mają pary,
Znajdzie się gotowych do tańca \(\displaystyle{ m}\) par i teraz jeszcze jedna rozkmina czy \(\displaystyle{ s \le m}\)
czy może: \(\displaystyle{ s > m}\) bo w takim razie pary te trzeba byłoby grupować po \(\displaystyle{ s}\)
plus reszta, która zostanie.
Na razie nie będę się tym bawił, założę roboczo, że wszystkie \(\displaystyle{ m}\) pary sobie na parkiecie tańczą i gra orkiestra.
I teraz ten sam taniec musi zatańczyć każda para spośród kobiet i panów na parkiecie partnerzy zmieniają się
\(\displaystyle{ m}\) razy
sposobów, potem znowu pozostałych panów ustawiam z paniami i dalej orkiestra nie zmienia nuty
zakładam, że: \(\displaystyle{ n=am+r}\)
czyli orkiestra nie zmienia nuty przez:
\(\displaystyle{ (a+1)m}\) tańców
a potem zaczyna się wszystko od początku bo idzie kolejny taniec.
To tak z grubsza...