Problem brydżysty

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Dilectus
Użytkownik
Użytkownik
Posty: 2662
Rejestracja: 1 gru 2012, o 00:07
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 369 razy

Problem brydżysty

Post autor: Dilectus »

Gram w brydża, ale nie potrafię już rozwiązać prostego problemu kombinatorycznego: Ile jest możliwych rozdań talii 52 kart czterem osobom? Pomóżcie...
robertm19
Użytkownik
Użytkownik
Posty: 1847
Rejestracja: 8 lip 2008, o 21:16
Płeć: Mężczyzna
Lokalizacja: Staszów/Warszawa
Podziękował: 7 razy
Pomógł: 378 razy

Problem brydżysty

Post autor: robertm19 »

Chyba \(\displaystyle{ \frac{52!}{(13!)^4}}\).
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

Problem brydżysty

Post autor: yorgin »

robertm19, potwierdzam jednocześnie rozwiewając dalsze wątpliwości.
Ukryta treść:    
Dilectus
Użytkownik
Użytkownik
Posty: 2662
Rejestracja: 1 gru 2012, o 00:07
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 369 razy

Problem brydżysty

Post autor: Dilectus »

Hmm... a ja myślę, że jest inaczej. Popatrzcie:
Pierwsze cztery karty można rozdać na \(\displaystyle{ {52 \choose 4}}\) sposoby, ale trzeba uwzględnić permutację tych czterech kart wśród graczy N, S, E, W, a więc na \(\displaystyle{ {52 \choose 4} \cdot 4!}\) sposobów.
Drugą czwórkę kart można rozdać na \(\displaystyle{ {52-4 \choose 4} \cdot 4!}\) sposobów,

k-tą czwórkę - na \(\displaystyle{ {52-4(k-1) \choose 4} \cdot 4!}\) sposobów itd.,

w końcu trzynastą - na \(\displaystyle{ {4 \choose 4}\cdot 4!}\) sposobów.

Ostatecznie mamy więc

\(\displaystyle{ \prod_{i=0}^{12} {52-4i \choose 4} \cdot 4! = 52!}\)

rozdań. Co Wy na to? - Mogę się oczywiście mylić...
Gouranga
Użytkownik
Użytkownik
Posty: 1565
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 243 razy

Problem brydżysty

Post autor: Gouranga »

Dilectus, ciekawy trop, jednak błędny. Zauważmy, że tym sposobem możemy np. z pierwszej czwórki dać graczowi N damę kier, a z drugiej asa pik, ale sytuacja, w której dajemy mu najpierw asa pik, potem damę kier jest tu rozważona jako odrębny przypadek a przecież wiemy, że kolejność rozdawania kart dla danego gracza nie ma znaczenia, dlatego prościej jest myśleć tak, że dajemy jednemu 13, potem drugiemu 13 itd. i wychodzi
\(\displaystyle{ {52 \choose 13}\cdot {39 \choose 13}\cdot {26 \choose 13}\cdot {13 \choose 13}}\)
Dilectus
Użytkownik
Użytkownik
Posty: 2662
Rejestracja: 1 gru 2012, o 00:07
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 369 razy

Problem brydżysty

Post autor: Dilectus »

Chyba niezupełnie, bo pierwszą trzynastkę możemy dać dowolnemu z czterech graczy, drugą - dowolnemu z trzech pozostałych, trzecią - dowolnemu z dwóch pozostałych. Mamy więc - idąc Twoim tropem myślenia - tyle rozdań:

\(\displaystyle{ {52 \choose 13}\cdot 4 \cdot {39 \choose 13} \cdot 3 \cdot {26 \choose 13} \cdot 2 \cdot {13 \choose 13} \cdot1 = {52 \choose 13}\cdot {39 \choose 13}\cdot {26 \choose 13}\cdot {13 \choose 13} \cdot 4! = \frac{52!}{(13!)^4} \cdot 4!}\)
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Problem brydżysty

Post autor: »

Dilectus, może łatwiej będzie Ci zrozumieć błąd w Twoim rozumowaniu na analogicznym, ale prostszym przykładzie.

Chcemy dać Zenonowi i Alfredowi żyrafę i hipopotama (jedno zwierzę dla jednej osoby). Zgodnie z Twoim rozumowaniem najpierw na \(\displaystyle{ \binom 21}\) sposobów wybieramy zwierzę dla pierwszej osoby, a potem na \(\displaystyle{ \binom 11}\) wybieramy zwierzę dla drugiej osoby, a potem - zgodnie z Twoim błędnym rozumowaniem - na \(\displaystyle{ 2!}\) sposobów przyporządkowujemy które zwierzę komu. Czyli łącznie są cztery sposoby (choć gołym okiem widać, że są tylko dwa).

Błąd polega na tym, że w ten sposób dwukrotnie ustalamy co dla kogo - raz losując zwierzęta (lub karty) kolejno, a drugi raz przy permutowaniu.

Jeśli upierasz się przy permutowaniu, to najpierw musiałbyś wylosować cztery trzynastki kart bez uwzględnienia kolejności, czyli policzyć ile jest podziałów zbioru \(\displaystyle{ 52}\)-elementowego na podzbiory \(\displaystyle{ 13}\)-elementowe (czyli bez uwzględnienia kolejności).

Q.
Gouranga
Użytkownik
Użytkownik
Posty: 1565
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 243 razy

Problem brydżysty

Post autor: Gouranga »

Dilectus pisze:Chyba niezupełnie, bo pierwszą trzynastkę możemy dać dowolnemu z czterech graczy, drugą - dowolnemu z trzech pozostałych, trzecią - dowolnemu z dwóch pozostałych. Mamy więc - idąc Twoim tropem myślenia - tyle rozdań:

\(\displaystyle{ {52 \choose 13}\cdot 4 \cdot {39 \choose 13} \cdot 3 \cdot {26 \choose 13} \cdot 2 \cdot {13 \choose 13} \cdot1 = {52 \choose 13}\cdot {39 \choose 13}\cdot {26 \choose 13}\cdot {13 \choose 13} \cdot 4! = \frac{52!}{(13!)^4} \cdot 4!}\)
To tak nie działa. Jeśli damy pierwszą trzynastkę graczowi N na \(\displaystyle{ {52 \choose 13}}\) sposobów, to w tym zawieramy każdą możliwą kombinację kart dla niego. Jeśli już rozdamy każdemu po 13 kart to jakiejkolwiek kombinacji by nie dostał jest ona zawarta już w tym założeniu.

A gdybyśmy już usilnie rozpisali to tamtym sposobem, że losujemy \(\displaystyle{ {52 \choose 4}}\) i na \(\displaystyle{ 4!}\) sposobów rozdajemy między graczy to końcowy wynik musielibyśmy podzielić przez \(\displaystyle{ \left(13!\right)^4}\) żeby wykluczyć permutacje w obrębie ręki każdego z graczy.

co zgodnie z wcześniejszymi obliczeniami daje nam

\(\displaystyle{ \frac{\prod_{i=0}^{12} {52-4i \choose 4} \cdot 4!}{(13!)^4} = \frac{52!}{(13!)^4} = {52 \choose 13}{39 \choose 13}{26 \choose 13}{13 \choose 13}}\)
Dilectus
Użytkownik
Użytkownik
Posty: 2662
Rejestracja: 1 gru 2012, o 00:07
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 369 razy

Problem brydżysty

Post autor: Dilectus »

Hmm... W Twoim przykładzie jest tyle zwierząt, ilu ludzi. Gdyby każda z osób miała dostać kilka zwierząt i ważny był ich "układ na jednej ręce", byłoby inaczej. Powiedz, Qń, co myślisz o takim moim rozumowaniu (cytuję sam siebie):
Pierwsze cztery karty można rozdać na \(\displaystyle{ {52 \choose 4}}\) sposoby, ale trzeba uwzględnić permutację tych czterech kart wśród graczy N, S, E, W, a więc na \(\displaystyle{ {52 \choose 4} \cdot 4!}\) sposobów
Drugą czwórkę kart można rozdać na \(\displaystyle{ {52-4 \choose 4} \cdot 4!}\) sposobów,

k-tą czwórkę - na \(\displaystyle{ {52-4(k-1) \choose 4} \cdot 4!}\) sposobów itd.,

w końcu trzynastą - na \(\displaystyle{ {4 \choose 4}\cdot 4!}\) sposobów.

Ostatecznie mamy więc

\(\displaystyle{ \prod_{i=0}^{12} {52-4i \choose 4} \cdot 4! = 52!}\)

rozdań. Co Wy na to? - Mogę się oczywiście mylić...
Gouranga
Użytkownik
Użytkownik
Posty: 1565
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 243 razy

Problem brydżysty

Post autor: Gouranga »

Przyszło mi do głowy jeszcze jedno, co wskazuje, że w Pana pomyśle z iloczynem jest błąd. Wyszło \(\displaystyle{ 52!}\) tak? Czyli ilość kombinacji jak możemy ułożyć wszystkie karty w talii, teraz tak potasowane karty dajemy graczom już bez rozdzielania na czwórki, N dostaje pierwsze 13 kart, W kolejne itd. (nie musimy ich dzielić na czwórki bo tasowanie jest zawarte już w \(\displaystyle{ 52!}\)). I teraz każdy w obrębie swojej ręki wyklucza permutacje więc dzielimy każdą rękę na \(\displaystyle{ 13!}\)
Awatar użytkownika
yorgin
Użytkownik
Użytkownik
Posty: 12762
Rejestracja: 14 paź 2006, o 12:09
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 17 razy
Pomógł: 3440 razy

Problem brydżysty

Post autor: yorgin »

Dilectus pisze:Gdyby każda z osób miała dostać kilka zwierząt i ważny był ich "układ na jednej ręce", byłoby inaczej.
Kolejność, w jakiej dostajesz karty, nie ma żadnego znaczenia. Bo czym się różni układ samych pików otrzymanych od dwójki do asa od układu otrzymanego od asa do dwójki?

Równoważne pytanie - czy przy losowaniu w lotto ma znaczenie, w jakiej kolejności wypadły dane liczby?
ODPOWIEDZ