szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 31 sie 2016, o 19:43 
Użytkownik

Posty: 45
Na balu jest 10 kawalerów i 12 panien (wszyscy rozróżnialni). Wszystkie panny potrafią tańczyć poloneza i walca oraz jedna potrafi również tańczyć tango. Kawalerowie podchodzą po kolei do panien i wybierają taniec. Na ile sposobów mogą odbyć się tańce, jeśli:
a) każda panna może tańczyć najwyżej z jednym kawalerem;
b) każda z panien może zostać poproszona do tańca kilka razy, w tym dziesięć.

Czy ktoś mógłby sprawdzić rozwiązanie? Wydaje mi się, że można zrobić to prościej albo się po prostu mylę i rozwiązanie jest błędne.

a) Każda panna może zatańczyć tylko raz. Oznaczmy pannę umiejącą zatańczyć trzy tańce jako X, mamy 3 przypadki:

1) X nie uczestniczy w tańcu:

wtedy do dyspozycji mamy 11 panien, ilość tańców to ilość funkcji różnowartościowych ze zbioru [10] w zbiór [11] pomnożona przez 2^{10} (uwzględniamy to, że każda para, a będzie ich 10, wybiera 1 z 2 tańców.
Zatem sposobów jest 11 \cdot 10...\cdot 2 \cdot 2^{10}

2)X tańczy:

Teraz postępujemy nieco inaczej - najpierw wybieramy partnera dla X (10 sposobów) i następnie taniec tej pary (3 sposoby). Następnie resztę par (będzie ich 9, bo tyle kawalerów zostało) na 10 \cdot 3 \cdot 11 \cdot 10... \cdot 3 \cdot 2^{9}

Łączna ilość sposobów to suma tych 2 rozłącznych przypadków.

b) Tutaj się komplikuje, bo nie wiemy, w ilu tańcach bierze udział X. Znów przypadki:

1) X nie tańczy tango lub nie uczestniczy w tańcach - 12^{10} \cdot 2^{10} sposobów

2) X tańczy tango. Musimy uwzględnić dowolną ilość tańców, w których bierze udział X (od 1 do 10)

Niech k oznacza liczbę tańców, w których uczestniczy X.
Najpierw wybieramy partnerów dla X (od 1 do 10) na {10 \choose k} sposobów, gdzie 1 \le k \le 10 i resztę tańców na 11^{10-k}  \cdot  2^{10-k}.

Zatem wszystkich sposobów w 2 przypadku jest \sum_{k=1}^{10}  {10 \choose k}  \cdot 11^{10-k}  \cdot 2^{10-k}.

Łącznie sposobów dla b) jest 12^{10} \cdot 2^{10} + \sum_{k=1}^{10}  {10 \choose k}  \cdot 11^{10-k}  \cdot 2^{10-k}.

Wydaje mi się, że to nie jest poprawne rozwiązanie, ale nie mogę znaleźć luki, tj. chyba wszystkie możliwości zliczyłem i żadnej nie opuściłem.
Góra
Mężczyzna Online
PostNapisane: 1 wrz 2016, o 09:57 
Użytkownik
Avatar użytkownika

Posty: 3326
Lokalizacja: blisko
Najpierw wybór par a potem suriekcje par do tańców odpowiednich.
Góra
Mężczyzna Offline
PostNapisane: 1 wrz 2016, o 10:52 
Użytkownik

Posty: 45
arek1357 napisał(a):
Najpierw wybór par a potem suriekcje par do tańców odpowiednich.


Suriekcje z jakiego zbioru? Dla każdego tańca (w zasadzie układu tańców) zliczamy liczbę ciągów długości 10, gdzie na i-tym (i-ty kawaler) miejscu jest liczba j (j-ta panna) dla 1 \le j \le 12 i każdej parze z ciągu przyporządkowujemy taniec. Jeśli chodzi o takie pary, to nie muszą być suriekcją. Co jeśli wszystkie pary z układu tańczą ten sam taniec? W dodatku i tak trzeba rozważyć przypadek, gdy X nie bierze udziału. Nie bardzo rozumiem, co miałeś na myśli.
Góra
Mężczyzna Online
PostNapisane: 2 wrz 2016, o 11:29 
Użytkownik
Avatar użytkownika

Posty: 3326
Lokalizacja: blisko
Suriekcje ze zbioru par w zbiór tańców. I wtedy nie przejmujesz się czy jest tylko jeden taniec trzy trzy...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 zadania ze zliczania  kriegor  0
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 Dwa SKOMPLIKOWANE zadania :)))  domel666  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl