szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 11:54 
Użytkownik

Posty: 35
Lokalizacja: Gdańsk
Na ile sposobów mogę rozmieścić 7 więźniów w 7 celach jeżeli:
a)Co najmniej jedna cela powinna zostać pusta
b)Dokładnie jedna cela powinna zostać pusta
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 13:03 
Użytkownik
Avatar użytkownika

Posty: 12431
Lokalizacja: czasem Warschau, czasem Breslau
a) wybieramy na siedem sposobów celę która ma być pusta i dalej rozdzielamy więźniów jakkolwiek do sześciu pozostałych, czyli mamy 7\cdot 6^7 sposobów rozmieszczenia (dla każdego z siedmiu więźniów mamy do wyboru sześć cel).

Co do b): czy możesz korzystać z liczb Stirlinga II rodzaju? Bo nie chce mi się tego liczyć "na piechotę".
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 13:41 
Użytkownik

Posty: 1007
Lokalizacja: Górnicza Dolina
Premislav napisał(a):
a) wybieramy na siedem sposobów celę która ma być pusta i dalej rozdzielamy więźniów jakkolwiek do sześciu pozostałych, czyli mamy 7\cdot 6^7 sposobów rozmieszczenia (dla każdego z siedmiu więźniów mamy do wyboru sześć cel).

Czy aby na pewno? Co jeśli 2 będą puste?
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 13:44 
Użytkownik
Avatar użytkownika

Posty: 12431
Lokalizacja: czasem Warschau, czasem Breslau
Przecież w podpunkcie a) co najmniej jedna cela ma zostać pusta, więc nie boli nas to, że np. dwie zostaną puste. Chyba że nie zrozumiałem Twojego zastrzeżenia.
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 13:48 
Użytkownik

Posty: 1007
Lokalizacja: Górnicza Dolina
Dobra ja coś sobie w głowie wymyśliłem, źle przeczytałem, sorry :)
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 14:52 
Użytkownik

Posty: 35
Lokalizacja: Gdańsk
Premislav napisał(a):
a) wybieramy na siedem sposobów celę która ma być pusta i dalej rozdzielamy więźniów jakkolwiek do sześciu pozostałych, czyli mamy 7\cdot 6^7 sposobów rozmieszczenia (dla każdego z siedmiu więźniów mamy do wyboru sześć cel).

Co do b): czy możesz korzystać z liczb Stirlinga II rodzaju? Bo nie chce mi się tego liczyć "na piechotę".

Na pierwszy rzut oka twoje rozwiązanie wydaje się sensowne.
Jednak gdy rozwiązuję je innym sposobem wychodzi inny wynik(może mój sposób jest zły).
Wygląda następująco:
1) Obliczam ilość wszystkich możliwości umieszczenia 7 więźniów w 7 celach: 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7=823543
2) Obliczam liczbę możliwości gdzie każda cela jest zajęta: 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1= 5040
3) Odejmuję od liczby wszystkich możliwości liczbę możliwości gdzie każda cela jest zajęta 823543-5040=818503

Zostają możliwości gdzie co najmniej jedna cela jest pusta.

Czy dobrze rozumuję? Jeżeli nie to gdzie popełniłem błąd?
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 17:55 
Użytkownik
Avatar użytkownika

Posty: 12431
Lokalizacja: czasem Warschau, czasem Breslau
Twój sposób jest poprawny, a mój nie, przepraszam (jak ja nienawidzę tej szkolnej kombinatoryki, nawet chyba w szkole dostałem z tego 4+ ze sprawdzianu). Policzyłem wielokrotnie te same ustawienia.
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 18:05 
Użytkownik

Posty: 35
Lokalizacja: Gdańsk
Premislav napisał(a):
Twój sposób jest poprawny, a mój nie, przepraszam (jak ja nienawidzę tej szkolnej kombinatoryki, nawet chyba w szkole dostałem z tego 4+ ze sprawdzianu). Policzyłem wielokrotnie te same ustawienia.


Dzięki za potwierdzenie. Jak w takim razie rozwiązać podpunkt b)?
Góra
Mężczyzna Offline
PostNapisane: 21 lip 2017, o 18:41 
Użytkownik
Avatar użytkownika

Posty: 12431
Lokalizacja: czasem Warschau, czasem Breslau
Takie niepoprawne rozumowanie, jak moje poprzednie do podpunktu a) chyba nawet jest przedstawione w książce Jakubowskiego i Sztencla Wstęp do rachunku prawdopodobieństwa (drugi rozdział zawiera też trochę elementarnej kombinatoryki), w paragrafie "najczęstsze błędy". :(

Co do podpunktu b).
Można użyć wspomnianych liczb Stirlinga II rodzaju, ale to niejawna postać i nie wiem, czy zostałaby zaakceptowana. Na 7 sposobów wybieramy pustą celę, dzielimy więźniów na sześć niepustych podgrup (podzbiorów) na \left\{7\atop 6\right\} sposobów i uwzględniamy jeszcze to, że cele są rozróżnialne, więc mnożymy przez 6!. Przy takim podejściu uzyksujemy wynik do b) w postaci 7! \cdot \left\{7\atop 6\right\}
Akurat tu to nie jest problem, bo \left\{7\atop 6\right\}={7\choose 2}, ogólnie \left\{n \atop n-1\right\}={n \choose 2}.

Choć może da się i bez liczb Stirlinga II rodzaju:
jak poprzednio, na 7 sposobów wybieramy celę, która ma być pusta. Następnie rozmieszczamy siedmiu więźniów w sześciu celach tak, aby żadna z tych sześciu nie była pusta. Na {7 \choose 2} sposobów wybieramy dwóch spośród siedmiu więźniów, którzy będą siedzieć w tej samej celi (skoro wszystkich sześć pozostałych cel należy zapełnić, to będzie tylko jedna taka para). Niejako sklejamy wówczas tę parę i traktujemy dalej jak jednego multiwięźnia (fajny neologizm), do 6 miejsc może trafić nasz "multiwięzień", a pozostałych pięciu rozmieszczamy w pozostałych pięciu celach na 5! sposobów. To daje nam taką odpowiedź do podpunktu b): 7\cdot {7\choose 2}\cdot 6!=7!{7\choose 2}=7!\cdot 21
Czy jest to zrozumiałe?
Góra
Mężczyzna Offline
PostNapisane: 24 lip 2017, o 14:19 
Użytkownik

Posty: 35
Lokalizacja: Gdańsk
Sposób bez liczb stringa bardzo dobrze objaśniony. Dzięki wielkie za pomoc :)))
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Na ile sposobów można rozdać talię kart  le3o  4
 na ile sposobów (...) - suma 2 liczb naturalnych  Undre  0
 Na ile sposobów można wybrać 10 piłek  piotrek20008  2
 Na ile sposobów można utworzyć pary?  momo  2
 Na ile sposobów... i szacowanie liczb  mkopmkop  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl