Majtki Batmana

[Gość: hetman_słoniowy]

Batman ma w szufladzie N majtek. Codziennie postępuje w następujący sposób:

1) Wstaje rano, otwiera szufladę i wybiera losowo jedne majtki (z równym
prawdopodobieństwem każde),
2) Wyjmuje gacie z suszarni (o ile są) i umieszcza w szufladzie,
3) Zwalcza zło w Gotham,
4) Wraca wieczorem i decyduje czy wrzucić gacie do pralki a potem do suszarni
(z prawdopodobieństwem P), czy od razu do szuflady.
5) Kładzie się spać.

Jakie jest prawdopodobieństwo, że w sobotę założy gacie, które już dokładnie
raz miał na sobie w tym tygodniu (zakładając, że w poniedziałek rano wszystkie
egzemplarze były w szufladzie)?

[smiechowiec]

Witaj Hetmanie
Trochę liczenia z tym zadaniem.
Na razie doszedłem do czwartku.
Prawdopodobieństwo, że w czwartek założy majtki, które już dokładnie
raz miał na sobie w tym tygodniu wynisi
Wzór w
postaci obrazka
bo texa tu chyba nie obsługują

[smiechowiec]

Jako, że jawny wzór na szukane prawdopodobieństwo jest dość długi, choć pewno da się go uprościć,
opiszę sposób w jaki możne je obliczyć postępując iteracyjne.
Oznaczenia :
C - liczba czystych majtek
B1 - liczba majtek użytych jednokrotnie
Bi - liczba majtek użytych i-krotnie
SC - liczba majtek czystych pobranych z szuflady
SBi - liczba majtek użytych i krotnie pobranych z szuflady


Stan początkowy C = N, B1 ... B5 = 0, liczba majtek w pralni 0
SC = C / (C + B1 + B2 + B3 + B4 + B5)
SB1 = B1 / (C + B1 + B2 + B3 + B4 + B5)
SBi = Bi / (C + B1 + B2 + B3 + B4 + B5)

Szukane prawdopodobieństwo dla sobotniego poranka wyraża się stosunkiem
B5 / (C + B1 + B2 + B3 + B4 + B5) po uwzględnieniu wartości z piątkowego wieczoru

Korzystając z numeracji zawartej w treści
1) Wstaje rano, otwiera szufladę i wybiera losowo jedne majtki (z równym
prawdopodobieństwem każde),
2) Wyjmuje gacie z suszarni (o ile są) i umieszcza w szufladzie,
4) Wraca wieczorem i decyduje czy wrzucić gacie do pralki a potem do suszarni
(z prawdopodobieństwem P), czy od razu do szuflady.


Poniedziałek
1) C = N - 1
2) brak majtek z pralni więc brak akcji
4) B1 = (1 - P) // tyle użytych jednokrotnie majtek wraca do szuflady, P majtek idzie do pralni

Wtorek
1) C = C - SC,
B1 = B1 - SB1
2) C = C + P
4) B1 = B1 + (1 - P)SC
B2 = B2 + (1 - P)SB1


Środa
1) C = C - SC,
B1 = B1 - SB1,
B2 = B2 - SB2
2) C = C + P
4) B1 = B1 + (1 - P)SC
B2 = B2 + (1 - P)SB1
B3 = B3 + (1 - P)SB2

itd. Ogólnie każdego kolejnego dnia mamy
1) C = C - SC,
Bi = Bi - SBi, (dla i od 1 do 5)
2) C = C + P
4) B1 = B1 + (1 - P)SC
Bi = Bi + (1-P) SB(i-1) (dla i od 2 do 5)

[Gość: hetman_sloniowy]

Witaj Śmiechowiec!

Na wstępie: gratuluję podjęcia wyzwania!

Od siebie na razie napiszę tylko tyle, że jeśli nie daje się (a czy się daje -
nie wiem) znaleźć sprawnie rozwiązania przy pomocy kartki i ołówka (czy,
ambitniej, 'w głowie'), to jak najbardziej wskazane jest skorzystanie z
odpowiedniego oprogramowania (cyberzagadka). Poza ostatecznym rozwiązaniem, mile
widziany skrypt lub opisany sposób dojścia do rozwiązania.

Proszę wybaczyć. Opisanego wyżej algorytmu dokładnie nie przeanalizowałem,
jednak pewne szczegóły nasuwają mi wątpliwości czy nie popełniono drobnych
uchybień w opisie bądź odmiennie zinterpretowano warunki zadania. Konkretnie,
chodzi mi o to, że liczba N to liczba całkowita, natomiast P to ułamek (a np.
B1, jak rozumiem, ma być liczbą całkowitą - stąd wątpliwość).

Pozdrawiam i liczę, że więcej osób podejmie wyzwanie!

[smiechowiec]

>Konkretnie, chodzi mi o to, że liczba N to liczba całkowita,
natomiast P to ułamek (a np.
>B1, jak rozumiem, ma być liczbą całkowitą - stąd wątpliwość).
Wydaje mi się, że zrozumiałem treść zgodnie z zamysłem autora,
a moja propozycja podejścia do problemu wydaje mi się nadal
prawidłowa, choć w mojej wypowiedzi zauważyłem pewne omyłki.

N - liczba początkowa majtek w szufladzie
P - prawdopodobieństwo przekazania używanych majtek do pralni czyli
liczba z zakresu od 0 do 1

Poza poniedziałkiem działania we wszystkie pozostałe dni wyglądają
identycznie,
więc postępowanie iteracyjne wydaje mi się uzasadnione.
Wzór bezpośredni wyliczyłem dla pierwszych dni, ale z powodu dużej
liczby mnożeń i konieczności upraszczania dla kolejnych dni zadanie
staje się dość żmudne więc nie kontynuowałem go.
Przy podejściu iteracyjnym w stosunkowo prosty sposób możemy
policzyć prawdopodobieństwa po dowolnej liczbie dni.

Prześledźmy co się dzieje dla przykładowej wartości N = 2, p = 0.5
1. W poniedziałek rano Batman pobiera 1 czyste majtki z szuflady.
4. Wieczorem wrzuca P majtek czyli 0.5 do pralni, a (1-P) czyli 0.5
do szuflady.
Mamy więc w szufladzie 1.5 majtek z czego 1 czyste i 0.5 majtek
używanych jednokrotnie.
Losując w poniedziałek rano losowo 1 majtki
wybierzemy używane z prawdopodobieństwem 0.5 / 1.5 = 1/3,
natomiast czyste z prawdopodobieństwem 1 / 1.5 = 2/3.

1. We wtorek rano Batman pobiera 1 majtki z szuflady.
Są one czyste z pp 2/3 i używane z pp 1/3 co wyliczyliśmy wyżej.
Wobec tego w szufladzie zostało 1 - 2/3 = 1/3 czystych majtek oraz
1/2 - 1/3 = 1/6 jednokrotnie użytych majtek
2. Z pralni do szuflady dokładamy P czyli 0.5 czystych majtek więc
ich liczba w szufladzie wyniesie 1/3 + 1/2 = 5/6
4. Wieczorem wrzuca P majtek czyli 0.5 do pralni, a (1-P) czyli 0.5
używanych do szuflady.
W związku z tym mamy w szufladzie 5/6 czystych majtek
1/6 używanych majtek + P czyli 1/2 używanych, z których 2/3 rano
były czyste więc jednokrotnie używanych mamy 1/3 + 1/6 = 1/2
pozostała część majtek czyli 1/3 z 1/2 = 1/6 to noszone już
wcześniej używane majtki czyli dwukrotnie noszone.

i tak dalej..

Prawdopodobieństwo wyciągnięcia majtek jednokrotnie używanych z
szuflady zawsze jest równe stosunkowi liczby majtek jednokrotnie
użytych, które znajdują się w szufladzie, do całkowitej liczby
majtek w szufladzie, która zawsze z rana (poza poniedziałkiem) jest
równa N -P bo P majtek znajduje się w pralni, w naszym przypadku
jest więc zawsze
w czasie losowania 1.5 majtek w szufladzie.

Kalkulator
majtek

[Gość: hetman_słoniowy]

Nie jestem przekonany czy rozumując w ten sposób (przyjmując niecałkowite liczby
majtek) dojdzie się do prawidłowego rozwiązania.

Dla N=2 i P=0.5 wychodzi mi, że prawdopodobieństwo wylosowania dokładnie raz
używanych majtek we wtorek wynosi 1/4 (a nie 1/3) - wnioskuję na podstawie
narysowanego 'drzewka'. Fakt, że we wtorek rano Batman może znaleźć się w 6
różnych sytuacjach, a tylko w dwóch z nich wybierze majtki, które już miał, ale
te 6 sytuacji nie zajdzie z równymi prawdopodobieństwami. Wymienię te sytuacje:

1) W poniedziałek miał majtki nr 1, wyprał je i we wtorek siłą rzeczy wybrał
majtki nr 2,
2) W poniedziałek miał majtki nr 1, nie wyprał ich i we wtorek wybór padł znowu
na majtki nr 1,
3) Jak w punkcie 2, ale we wtorek wybór padł na majtki nr 2,
4) W poniedziałek miał majtki nr 2, wyprał je i we wtorek siłą rzeczy wybrał
majtki nr 1,
5) W poniedziałek miał majtki nr 2, nie wyprał ich i we wtorek wybór padł znowu
na majtki nr 2,
6) Jak w punkcie 5, ale we wtorek wybór padł na majtki nr 1.

Prawdopodobieństwa poszczególnych zdarzeń:
1) 1/4
2) 1/8
3) 1/8
4) 1/4
5) 1/8
6) 1/8

Ponieważ nas interesują zdarzenia nr 2 i nr 5 to suma ich prawdopodobieństw daje
1/4.

[smiechowiec]

Gość portalu: hetman_słoniowy napisał(a):
> Nie jestem przekonany czy rozumując w ten sposób (przyjmując
niecałkowite liczby
> majtek) dojdzie się do prawidłowego rozwiązania.
Masz rację, trochę za bardzo uprościłem sprawę.
Prawdopodobioeństwa kolejnych działań są zależne od wyników
poprzednich w związku z tym wydaje mi się że złozoność wzoru narasta
wykładniczo.
Drzewko, do analizy dla sobotniego ranka ma 648 gałezi...
Na jego podstawie, dla podanych wartości p = 0.5 i 2 par majtek
wyliczyłem to jako
Wtorek, czyste = 0.75, jednokrotnie uzyte = 0.25, wiecej niz raz 0
Sroda czyste = 0.5625, jednokrotnie uzyte = 0.375, wiecej niz raz
0.0625
czwartek, czyste = 0.507813, jednokrotnie uzyte = 0.335938, wiecej
niz raz 0.15625
Piatek, czyste = 0.486654, jednokrotnie uzyte = 0.297526, wiecej niz
raz 0.21582
Sobota, czyste = 0.472493, jednokrotnie uzyte = 0.287638, wiecej niz
raz 0.239868

[huius_universitatis]

A jaką rolę w zadaniu pełni kwestia prania? W tak skonstruowanym zadaniu nie ma to żadnego znaczenia. Może w Twoim pytaniu chodziło o to, jakie jest prawdopodobienstwo, ze w sobote zalozy CZYSTE (lub BRUDNE) majtki, a nie majtki, ktore byly wczesniej noszone tylko raz?

Jesli jednak pytanie brzmi rzeczywiscie tak, jak je stawiasz, to rozwiazanie jest nastepujace: ponumerujmy majtki od 1 do N i rozwazmy wszystkie 5-elementowe ciagi (p1,p2,p3,p4,p5), gdzie pi jest numerem majtek, ktore zostaly wyciagniete w i-tym dniu. Wszystkich ciagow jest N^5. Interesuja nas wylacznie ciagi, w ktorych pewna liczba wystepuje dokladnie raz. Jesli wsrot tych 5 liczb dokladnie k wystepuje jednokrotnie, to dla takiej sytuacji prawdopodobienstwo zalozenia w sobote jednokrotnie uzytych majtek wynosi k/N. Jakie mamy sytuacje, jesli idzie o licznosci wystepowania liczb w ciagu (interesuja nas tylko te, w ktorych istnieje przynajmniej jedna liczba wystepujaca jednokrotnie):

1+1+1+1+1 (5 majtek, kazde zalozone raz)
Pr1 = ((N po 5)/(N^5))*(5/N)

1+1+1+2 (3 majtki zalozone jednokrotnie, jedne dwukrotnie)
Pr2 = ((N*(5 po 2)*(N-1 po 3))/(N^5))*(3/N)

1+2+2 (1 majtki zalozone jednokrotnie, dwa dwukrotnie)
Pr3 = ((N*(5 po 2)*(N-1)*(3 po 2)*(N-2))/(N^5))*(1/N)

1+1+3
Pr4 = (N*(5 po 3)*(N-1 po 2)/(N^5))*(2/N)

1+4
Pr5 = ((N*(5 po 4)*(N-1 po 1))/(N^5))*(1/N)

Szukane prawdopodobienstwo do Pr1+Pr2+Pr3+Pr4+Pr5.


Jesli jednak chodzilo Ci o to, czy w sobote zalozy czyste majtki, to rozwiazanie jest nastepujace: niech P(d,k) oznacza prawdopodobienstwo, ze w dniu d w szufladzie jest k czystych majtek. Mamy P(1,N)=1, P(1,k)=0 dla k=0,...,N-1. Latwo zauwazyc, ze zachodzi nastepujaca zaleznosc:

P(d,k)=SUMA(k=1..N) [ P(d-1,k)*((1-P(d-1,k))*P+P(d-1,k)*P) ], czyli prosciej:

P(d,k)=P*SUMA(k=1..N) P(d-1,k). Zatem, korzystajac z wzoru na prawdopodobienstwo calkowite, obliczamy szukane prawdopodobienstwo ubrania czystych majtek jako P*SUMA(k=1..N) P(d-1,k)*(k/N). Prawdopodobnie da sie uzyskac zwarta postac tego wzoru uzywajac funkcji tworzacych.

Pozdrawiam

[smiechowiec]

huius_universitatis napisał:
> A jaką rolę w zadaniu pełni kwestia prania?
> W tak skonstruowanym zadaniu nie ma to żadnego znaczenia.
Wydaje mi się, że ma choć rzeczywiście nie jest wprost napisane, że
majtki noszone po wypraniu są uznane za czyste
i traktowane są dale nie jak użyte, ale już wybór ze zbioru
mniejszego niż N, w niektóre poranki , z powodu prania majtek,
należy koniecznie uwzględnić.

Rozrysowałem drzewko jakie zaproponował autor i wypisałem
poszczególne prawdopodobieństwa,
po zsumowaniu i uporządkowaniu, wzór ogólny na prawdopodobieństwo
wyciągnięcia jednokrotnie użytych majtek, które nie były później
prane, w sobotni poranek wynosi
6 * (1-P)^5 * N^-5
+ 23 * (1-P)^5 * N^-5 * (N-1)
+ 32 * (1-P)^5 * N^-5 * (N-1) * (N-2)
+ 19 * (1-P)^5 * N^-5 * (N-1) * (N-2) * (N-3)
+ 5 * (1-P)^5 * N^-5 * (N-1) * (N-2) * (N-3) * (N-4)
+ (1-P)^5 * N^-5 * (N-1) * (N-2) * (N-3) * (N-4) * (N-5)
+ 3 * P * (1-P)^4 * N^-3 * (N-1)^-1
+ 47 * P * (1-P)^4 * N^-4
+ 39 * P * (1-P)^4 * N^-4 * (N-1)
+ 22 * P * (1-P)^4 * N^-4 * (N-1) * (N-2)
+ 6 * P * (1-P)^4 * N^-4 * (N-1) * (N-2) * (N-3)
+ P * (1-P)^4 * N^-4 * (N-1) * (N-2) * (N-3) * (N-4)
+ 10 * P * (1-P)^4 * N^-4 * (N-1)^-1
+ 54 * P * (1-P)^4 * N^-4 * (N-2)
+ 27 * P * (1-P)^4 * N^-4 * (N-2) * (N-3)
+ 6 * P * (1-P)^4 * N^-4 * (N-2) * (N-3) * (N-4)
+ P * (1-P)^4 * N^-4 * (N-2) * (N-3) * (N-4) * (N-5)
+ P * (1-P)^4 * N^-4 * (N-2) * (N-3) * (N-4)^2
+ 6 * P * (1-P)^4 * N^-4 * (N-2) * (N-3)^2
+ P * (1-P)^4 * N^-4 * (N-2) * (N-3)^2 * (N-4)
+ 26 * P * (1-P)^4 * N^-4 * (N-2)^2
+ 6 * P * (1-P)^4 * N^-4 * (N-2)^2 * (N-3)
+ P * (1-P)^4 * N^-4 * (N-2)^2 * (N-3) * (N-4)
+ 3 * P^2 * (1-P)^3 * N^-2 * (N-1)^-2
+ 52 * P^2 * (1-P)^3 * N^-3
+ 24 * P^2 * (1-P)^3 * N^-3 * (N-1)
+ 7 * P^2 * (1-P)^3 * N^-3 * (N-1) * (N-2)
+ P^2 * (1-P)^3 * N^-3 * (N-1) * (N-2) * (N-3)
+ 15 * P^2 * (1-P)^3 * N^-3 * (N-1)^-1
+ 25 * P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2)
+ 9 * P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2) * (N-3)
+ P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2) * (N-3) * (N-4)
+ P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2) * (N-3) * (N-4)^2
+ 7 * P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2) * (N-3)^2
+ P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2) * (N-3)^2 * (N-4)
+ P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2) * (N-3)^3
+ 34 * P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2)^2
+ 8 * P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2)^2 * (N-3)
+ P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2)^2 * (N-3) * (N-4)
+ P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2)^2 * (N-3)^2
+ 7 * P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2)^3
+ P^2 * (1-P)^3 * N^-3 * (N-1)^-1 * (N-2)^3 * (N-3)
+ 3 * P^2 * (1-P)^3 * N^-3 * (N-1)^-2
+ 38 * P^2 * (1-P)^3 * N^-3 * (N-2)
+ 7 * P^2 * (1-P)^3 * N^-3 * (N-2) * (N-3)
+ P^2 * (1-P)^3 * N^-3 * (N-2) * (N-3) * (N-4)
+ P^2 * (1-P)^3 * N^-3 * (N-2) * (N-3)^2
+ 8 * P^2 * (1-P)^3 * N^-3 * (N-2)^2
+ P^2 * (1-P)^3 * N^-3 * (N-2)^2 * (N-3)
+ 28 * P^3 * (1-P)^2 * N^-2
+ 8 * P^3 * (1-P)^2 * N^-2 * (N-1)
+ P^3 * (1-P)^2 * N^-2 * (N-1) * (N-2)
+ 14 * P^3 * (1-P)^2 * N^-2 * (N-1)^-1 * (N-2)
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-1 * (N-2) * (N-3)
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-1 * (N-2) * (N-3)^2
+ 10 * P^3 * (1-P)^2 * N^-2 * (N-1)^-1 * (N-2)^2
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-1 * (N-2)^2 * (N-3)
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-1 * (N-2)^3
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2) * (N-3)
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2) * (N-3)^2
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2) * (N-3)^3
+ 7 * P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2)^2
+ 2 * P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2)^2 * (N-3)
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2)^2 * (N-3)^2
+ 8 * P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2)^3
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2)^3 * (N-3)
+ P^3 * (1-P)^2 * N^-2 * (N-1)^-2 * (N-2)^4
+ 10 * P^3 * (1-P)^2 * N^-2 * (N-2)
+ P^3 * (1-P)^2 * N^-2 * (N-2) * (N-3)
+ P^3 * (1-P)^2 * N^-2 * (N-2)^2
+ 9 * P^4 * (1-P) * N^-1
+ P^4 * (1-P) * N^-1 * (N-1)
+ 3 * P^4 * (1-P) * N^-1 * (N-1)^-1 * (N-2)
+ P^4 * (1-P) * N^-1 * (N-1)^-1 * (N-2)^2
+ 2 * P^4 * (1-P) * N^-1 * (N-1)^-2 * (N-2)^2
+ P^4 * (1-P) * N^-1 * (N-1)^-2 * (N-2)^3
+ P^4 * (1-P) * N^-1 * (N-1)^-3 * (N-2)^3
+ P^4 * (1-P) * N^-1 * (N-1)^-3 * (N-2)^4
+ P^4 * (1-P) * N^-1 * (N-2)
+ P^5

przez symbol a* b należy rozumieć liczbę a pomnożona przez b
przez symbol a^b należy rozumieć liczbę a podniesioną do potęgi b

[hetman_sloniowy]

Podziwiam pracowitość i umiejętności przedmówców. Widać, zdecydowanie
przesadziłem - wystarczyłoby pewnie zatrzymać się na środzie, aby zadanie nie
było mozolną katorgą. Gratuluję tym, którzy przez nią przebrnęli.

[Gość: szatan]

get a life people!!!