Mamy następujący problem:
W pudełkach ponumerowanych od 1 do 200 znajdują się kartki z numerami od 1 do 200 rozmieszczone w sposób losowy. Sto osób zostało ponumerowanych liczbami od 1 do 100. Osoba z numerem 1 otwiera pudełko z numerem 1, wyciąga kartkę i następnie otwiera pudełko z odczytanym numerem. Z kolejnymi pudełkami postępuje tak samo, do momentu gdy wróci do pudełka numer jeden. Każda z kolejnych osób postępuje analogicznie, z tym, że osoba z numerem \(\displaystyle{ k}\) zaczyna od pudełka z numerem \(\displaystyle{ k}\) i kończy swój cykl na nim. Jakie jest prawdopodobieństwo, że wszystkie 100 osób wróci do swojego pudełka po co najwyżej stu "ruchach". Podobno wyniesie ono ponad \(\displaystyle{ \frac{1}{4}}\). Jak się za to zabrać?
Prawdopodobieństwo wystąpienia cyklu
- kristoffwp
- Użytkownik
- Posty: 688
- Rejestracja: 28 gru 2009, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Bielsko - Biała
- Podziękował: 20 razy
- Pomógł: 88 razy
- kristoffwp
- Użytkownik
- Posty: 688
- Rejestracja: 28 gru 2009, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Bielsko - Biała
- Podziękował: 20 razy
- Pomógł: 88 razy
- kristoffwp
- Użytkownik
- Posty: 688
- Rejestracja: 28 gru 2009, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Bielsko - Biała
- Podziękował: 20 razy
- Pomógł: 88 razy
-
- 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
Prawdopodobieństwo wystąpienia cyklu
Oczywiście \(\displaystyle{ |\Omega |=200!}\).
Zauważmy, że zdarzenie przeciwne \(\displaystyle{ A'}\) polega na tym, że w permutacji naszego zbioru \(\displaystyle{ 200}\)-elementowego pojawi się cykl długości \(\displaystyle{ k\ge 101}\). Permutacji w których pojawi się cykl takiej długości jest:
\(\displaystyle{ \binom{200}{k}\cdot (k-1)! \cdot (200-k)! = \frac{200!}{k}}\)
(kolejno: wybieramy \(\displaystyle{ k}\) elementów do cyklu, traktując dowolny element jako początek cyklu ustalamy kolejność następnych \(\displaystyle{ k-1}\) elementów cyklu, permutujemy pozostałe \(\displaystyle{ 200-k}\) elementów)
W takim razie:
\(\displaystyle{ P(A') = \frac{\sum_{k=101}^{200}\frac{200!}{k}}{200!} = \sum_{k=101}^{200}\frac{1}{k} \approx \ln 200 - \ln 100 = \ln 2}\)
a zatem:
\(\displaystyle{ P(A)=1- \ln 2 \approx 0,31}\)
Q.
Zauważmy, że zdarzenie przeciwne \(\displaystyle{ A'}\) polega na tym, że w permutacji naszego zbioru \(\displaystyle{ 200}\)-elementowego pojawi się cykl długości \(\displaystyle{ k\ge 101}\). Permutacji w których pojawi się cykl takiej długości jest:
\(\displaystyle{ \binom{200}{k}\cdot (k-1)! \cdot (200-k)! = \frac{200!}{k}}\)
(kolejno: wybieramy \(\displaystyle{ k}\) elementów do cyklu, traktując dowolny element jako początek cyklu ustalamy kolejność następnych \(\displaystyle{ k-1}\) elementów cyklu, permutujemy pozostałe \(\displaystyle{ 200-k}\) elementów)
W takim razie:
\(\displaystyle{ P(A') = \frac{\sum_{k=101}^{200}\frac{200!}{k}}{200!} = \sum_{k=101}^{200}\frac{1}{k} \approx \ln 200 - \ln 100 = \ln 2}\)
a zatem:
\(\displaystyle{ P(A)=1- \ln 2 \approx 0,31}\)
Q.
- kristoffwp
- Użytkownik
- Posty: 688
- Rejestracja: 28 gru 2009, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Bielsko - Biała
- Podziękował: 20 razy
- Pomógł: 88 razy
Prawdopodobieństwo wystąpienia cyklu
Dziękuję za pomoc. Wiedziałem, że trzeba liczyć prawdopodobieństwo zdarzenia przeciwnego, ale nie wpadłem na to, jak się zabrać za ten 101+ elementowy cykl.