szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 cze 2017, o 13:26 
Użytkownik

Posty: 3
Lokalizacja: pl
Cześć, mam problem z tym zadaniem z matematyki dyskretnej, ponieważ ten dział nie jest moją mocną stroną, więc chciałbym dowiedzieć jak rozwiązać to zadanie?
Cytuj:
Rzucamy n-krotnie monetą. Serią nazwiemy wypadnięcie najmniej 3 razy pod rząd tego samego wyniku. Niech b_{n} oznacza liczbę tych wyników, które nie zawierają serii. Znajdź i uzasadnij wzór rekurencyjny dla ciągu b^{\infty}_{n=0}
.
Góra
Mężczyzna Offline
PostNapisane: 28 cze 2017, o 13:56 
Użytkownik

Posty: 12648
Powiedzmy, że w ciągu kolejnych rzutów długości n nie wystąpiła żadna seria.
Jeżeli ten ciąg rzutów nie kończył się wystąpieniem dokładnie dwóch orłów/dwóch reszek w dwóch ostatnich rzutach, to w n+1. rzucie może wypaść cokolwiek i dalej nie będzie serii. Natomiast jeżeli ciąg n rzutów bez serii skończył się wypadnięciem dokładnie dwóch orłów bądź dokładnie dwóch reszek, to mamy tylko jedną możliwość, by po n+1 rzutach dalej serii nie było (odpowiednio reszka w n+1. rzucie bądź w drugim wypadku orzeł w n+1. rzucie). Niech x_n oznacza liczbę wyników długości n bez serii, które kończą się dwoma takimi samymi wynikami cząstkowymi (orzeł, orzeł lub reszka, reszka).
Wówczas b_{n+1}=2(b_n-x_n)+x_n=2b_n-x_n
Z drugiej strony, x_{n+1}=b_n-x_n, co łatwo widać: x_{n+1} to liczba wyników przy rzucie n+1 razy, w których nie ma serii, zaś w dwóch ostatnich rzutach wypadło to samo, czyli każdy taki wynik długości n+1 powstaje przez "dopisanie" do wyniku bez serii po n rzutach, gdzie na końcu nie ma dwóch takich samych (jakby były, to w n+1. rzucie albo zrobilibyśmy serię, której miało nie być, albo nie sparowalibyśmy) wyników cząstkowych
w n+1. rzucie tego samego wyniku cząstkowego, co w n. rzucie.
Mamy więc taki układzik:
\begin{cases} b_{n+1}=2b_n-x_n \\ x_{n+1}=b_n-x_n\end{cases}
Wstawiając z pierwszego równania do drugiego x_n=2b_n-b_{n+1}
otrzymujemy
x_{n+1}=b_{n+1}-b_n, stąd dla n \ge 2 jest x_n=b_n-b_{n-1}
i ostatecznie b_{n+1}=2b_n-b_n+b_{n-1}=b_n+b_{n-1}, n \ge 2
czyli równanie a la Fibonacci.
Ponadto b_1=2, b_2=4
Góra
Mężczyzna Offline
PostNapisane: 26 sie 2017, o 18:05 
Użytkownik
Avatar użytkownika

Posty: 187
Lokalizacja: brak
Nie można pokusić się o bezpośrednie uzasadnienie równości b_n = 2f_n?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rzuty monetą - zadanie 12  arek1  9
 rzut monetą - zadanie 30  Carlj28  9
 Rzut kostką - zmienna losowa  ŚwIeRsZcZ  0
 Rzut n krotnie kostką do gry  thor90  5
 Rzut kostką... - zadanie 3  Pawelloo  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl