Przeskocz do treści

Delta mi!

Złośliwe świnki

Jacek Jakubowski i Rafał Sztencel

o artykule ...

  • Publikacja w Delcie: czerwiec 2004
  • Publikacja elektroniczna: 22-05-2011
  • Autor: Rafał Sztencel
    Notka biograficzna: Rafał Sztencel (1953-2008) - były pracownik Instytutu Matematyki UW i wieloletni współpracownik Delty.

W dziale naukowym jednej z gazet pojawiło się następujące zadanie...

Zadanie. Jest sto skarbonek (to tytułowe świnki) z kluczykami. Każdy kluczyk pasuje tylko do jednej skarbonki. Skarbonki zamykamy, a wymieszane losowo kluczyki wrzucamy po jednym do każdej skarbonki. Teraz tłuczemy jedną skarbonkę, a wyjętym z niej kluczykiem otwieramy następną, etc. Jaka jest szansa, że pozostałe skarbonki uda się otworzyć bez rozbijania?

Do wyboru były cztery odpowiedzi: a)  math b)  math c)  math d)  math Wielu czytelników uważało jednak, że żadna z podanych odpowiedzi nie jest prawdziwa, na ogół z powodu skojarzenia z dobrze znanym zadaniem o kapeluszach: jeśli math osób włoży losowo math kapeluszy, to z prawdopodobieństwem równym

display-math

żadna z nich nie będzie miała swojego kapelusza na głowie.

Co gorsza, piszący te słowa obserwowali to zjawisko na sobie i swoich studentach. Pierwszym odruchem była uwaga:
aha, jeśli żaden kluczyk nie znajdzie się w skarbonce, którą otwiera, to otworzymy po kolei wszystkie.
Owszem, jest to warunek konieczny, ale nie dostateczny. Otóż operacja uda się wtedy i tylko wtedy, gdy kluczyk od rozbitej skarbonki pojawi się na końcu. A szansa na to – ze względu na symetrię – jest równa math Gdyby ktoś nie wierzył, może rozwiązać zadanie formalnie. Rozważmy math skarbonek. Zdarzeniami elementarnymi, które uznajemy za jednakowo prawdopodobne, są math-elementowe ciągi kluczyków. Takich ciągów jest math zdarzeniami sprzyjającymi są zaś te, w których kluczyk od rozbitej skarbonki pojawia się na końcu. Jest ich math stąd szukane prawdopodobieństwo wynosi

display-math

Niestety, właściwe rozwiązanie przychodzi zwykle do głowy poniewczasie. Świnki są naprawdę złośliwe. Dlatego będziemy je tłuc bardziej intensywnie.

Załóżmy, że w chwili pojawienia się kluczyka niepasującego do żadnej skarbonki tłuczemy kolejną. Ile  średnio trzeba stłuc skarbonek, by otworzyć wszystkie?

Czytelnik może spróbować odgadnąć rząd wielkości. Średnia jest zaskakująco nieduża i wynosi

display-math

Dla math skarbonek średnia, którą oznaczymy przez math jest równa math-tej sumie częściowej szeregu harmonicznego:

display-math

gdzie math jest stałą Eulera. Jak widać, math rośnie wraz z math dość powoli.

Jak uzyskać ten wynik?

Sposób 1. Jeśli stłuczemy pierwszą świnkę, to pasujący do niej kluczyk ma równe szanse pojawienia się jako pierwszy, drugi, itd. Wtedy zadanie sprowadza się do otwarcia pozostałych math  math itd. skarbonek w ten sam sposób. Dlatego

display-math

Mamy zatem dla math:

pict

Z równania (2) wynika, że

display-math(3)

i odjęcie stronami (3) od (1) daje math czyli math dla math Ostatecznie

display-math

Jak zwykle, poniewczasie wpadamy na inny pomysł, prowadzący do prostszych rachunków.



Sposób 2. Po stłuczeniu pierwszej świnki mamy szansę math znalezienia tam pasującego do niej kluczyka; wtedy pozostaje do otwarcia średnio math skarbonek. W przeciwnym razie jesteśmy w stanie otworzyć kolejną skarbonkę (nie musimy jej tłuc), zatem pozostaje średnio math skarbonek do otwarcia. Stąd równanie:

display-math

Rozwiązując zadanie, korzystaliśmy tak naprawdę z pojęcia warunkowej wartości oczekiwanej. Przypomnijmy, że zwykła wartość oczekiwana dla zmiennej losowej przyjmującej skończenie wiele wartości math jest dana wzorem

display-math(4)

Jeśli teraz wprowadzimy zdarzenie math  (takie, że math ) i zastąpimy we wzorze (4) zwykłe prawdopodobieństwo przez warunkowe, otrzymamy średnią wartość math  na math :

display-math(5)

Jeżeli dane jest rozbicie math przestrzeni zdarzeń elementarnych math na zdarzenia math  to definiujemy warunkową wartość oczekiwaną math  pod warunkiem math jako zmienną losową, która przyjmuje wartości math  na math :

display-math(6)


Wtedy można łatwo udowodnić odpowiednik wzoru na prawdopodobieństwo całkowite:

display-math(7)

Oto dowód:

pict

Wyrażenie (9) otrzymaliśmy, korzystając z (5). Po zamianie kolejności sumowania równość wyrażeń (10) i (11) wynika oczywiście ze wzoru na prawdopodobieństwo całkowite.

Dwa rozwiązania zadania o średniej liczbie stłuczonych świnek ilustrują typowe zastosowania wzoru (7), który umożliwia układanie równań. Mieliśmy do czynienia z dwoma rozbiciami przestrzeni math na (wykluczające się!) zdarzenia: w sposobie 1 ze względu na chwilę pojawienia się kluczyka od pierwszej stłuczonej świnki, w sposobie 2 – ze względu na to, czy miała w środku swój kluczyk, czy też nie. Można było łatwo odgadnąć, bez zbędnych formalizmów, czemu są równe średnie math