Zadanie mikołajkowe Piotrek: Na kanale Numberphile pojawił się ostatnio taki filmik https://www.youtube.com/watch?v=5kC5k5QBqcc Każdy z nas zna szkolne losowanie na mikołajki Zasady są takie: każdy losuje po kolei osobę, której ma kupić prezent. Jeśli wylosujemy siebie los trafia z powrotem do kapelusza, my losujemy ponownie, później kolejna osoba i tak dalej aż do wyczerpania losów. Problem jest następujący: jakie jest prawdopodobieństwo, że gdy losuje 20 osób w kapeluszu zostanie ostatni los, ostatnia osoba trafi na siebie a losowanie trzeba będzie powtórzyć? Np. jeśli mamy 3 osoby A,B,C mamy 6 przypadków losowań, jednak tylko 3 z nich są prawidłowe Obrazki jak nasze drzewko wygląda − http://i.imgur.com/jyud528.png http://i.imgur.com/UUADl2W.png Zaczynamy, A losuje 1. A−>B−>C − nie bierzemy pod uwagę, ponieważ A wyciągnął siebie 2. A−>C−>B − tak samo, odrzucamy, A wyciągnął siebie 3. B−>C−>A − losowanie udane, prawdopodbieństwo 1/2*1/2 = 25% 4. B−>A−>C − KLOPS! Losowanie należy powtórzyć. C jako ostatni wyciągnął siebie, losowanie do powtórzenia (prawdopodobieństwo zajścia 25%) 5. C−>A−>B − losowanie udane, szansa takiego zdarzenia 50% 6. C−>B−>A − również odrzucamy, B wyciągnął siebie Czyli, dla 3 osób losowanie trzeba będzie powtórzyć w 25%. (widzimy, że jeśli A wyciągnie B, to B może wyciągnąć tylko C jak w przypadku nr 3. Natomiast jak A wybierze C, no to już wtedy osoba B ma 2 opcje ) Teraz tak. W filmie pada stwierdzenie, ze gdy mamy 20 osób losowanie trzeba będzie powtórzyć w 4%, natomiast nie potrafię do tego dojść. Stworzyłem sobie drzewko dla 4 osób A,B,C,D W takim przypadku niepowodzenie wyszło w 5/36 ~ 14% Mamy 4! = 24 dróg Jednak od razu odrzucamy przypadki, kiedy A wylosuje siebie. Odpada 6 dróg [n!(1−¹_n)] Narysowałem te 18 pozostałych dróg drzewka z któych musiałem odliczyć przypadki gdzie osoby w kolejnych etapach wylosowały siebie, czyli BACD BDCA CBAD CBDA DACB DBAC DBCA Ostatecznie zostało 11 dróg. Z czego D wylosował siebie jako ostatni w przypadkach B,C,A,D oraz C,A,B,D

	1		1		1		1
P(B,C,A,D)=		*		*		=
	3		3		2		18

	1		1		1		1
P(C,A,B,D) =		*		*		=
	3		2		2		12

1		1		5
	+		=		. Czyli dla 4 osób losowanie do powtórki w około 14% przypadków.
18		12		36

Oczywiście rysowanie drzewek dla 20 osób jest niewykonalne Jak to sprawnie policzyć, macie jakiś pomysł?