.Rzucamy n-krotnie monetą. Serią nazwiemy wypadnięcie najmniej 3 razy pod rząd tego samego wyniku. Niech \(\displaystyle{ b_{n}}\) oznacza liczbę tych wyników, które nie zawierają serii. Znajdź i uzasadnij wzór rekurencyjny dla ciągu \(\displaystyle{ b^{\infty}_{n=0}}\)
Rzut n-krotnie monetą(..)
Rzut n-krotnie monetą(..)
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?
Ostatnio zmieniony 28 cze 2017, o 14:48 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: \infty.
Powód: Poprawa wiadomości: \infty.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Rzut n-krotnie monetą(..)
Powiedzmy, że w ciągu kolejnych rzutów długości \(\displaystyle{ 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 \(\displaystyle{ n+1}\). rzucie może wypaść cokolwiek i dalej nie będzie serii. Natomiast jeżeli ciąg \(\displaystyle{ 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 \(\displaystyle{ n+1}\) rzutach dalej serii nie było (odpowiednio reszka w \(\displaystyle{ n+1}\). rzucie bądź w drugim wypadku orzeł w \(\displaystyle{ n+1}\). rzucie). Niech \(\displaystyle{ x_n}\) oznacza liczbę wyników długości \(\displaystyle{ n}\) bez serii, które kończą się dwoma takimi samymi wynikami cząstkowymi (orzeł, orzeł lub reszka, reszka).
Wówczas \(\displaystyle{ b_{n+1}=2(b_n-x_n)+x_n=2b_n-x_n}\)
Z drugiej strony, \(\displaystyle{ x_{n+1}=b_n-x_n}\), co łatwo widać: \(\displaystyle{ x_{n+1}}\) to liczba wyników przy rzucie \(\displaystyle{ 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 \(\displaystyle{ n+1}\) powstaje przez "dopisanie" do wyniku bez serii po \(\displaystyle{ 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 \(\displaystyle{ n+1}\). rzucie tego samego wyniku cząstkowego, co w \(\displaystyle{ n}\). rzucie.
Mamy więc taki układzik:
\(\displaystyle{ \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 \(\displaystyle{ x_n=2b_n-b_{n+1}}\)
otrzymujemy
\(\displaystyle{ x_{n+1}=b_{n+1}-b_n}\), stąd dla \(\displaystyle{ n \ge 2}\) jest \(\displaystyle{ x_n=b_n-b_{n-1}}\)
i ostatecznie \(\displaystyle{ 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 \(\displaystyle{ b_1=2, b_2=4}\)
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 \(\displaystyle{ n+1}\). rzucie może wypaść cokolwiek i dalej nie będzie serii. Natomiast jeżeli ciąg \(\displaystyle{ 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 \(\displaystyle{ n+1}\) rzutach dalej serii nie było (odpowiednio reszka w \(\displaystyle{ n+1}\). rzucie bądź w drugim wypadku orzeł w \(\displaystyle{ n+1}\). rzucie). Niech \(\displaystyle{ x_n}\) oznacza liczbę wyników długości \(\displaystyle{ n}\) bez serii, które kończą się dwoma takimi samymi wynikami cząstkowymi (orzeł, orzeł lub reszka, reszka).
Wówczas \(\displaystyle{ b_{n+1}=2(b_n-x_n)+x_n=2b_n-x_n}\)
Z drugiej strony, \(\displaystyle{ x_{n+1}=b_n-x_n}\), co łatwo widać: \(\displaystyle{ x_{n+1}}\) to liczba wyników przy rzucie \(\displaystyle{ 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 \(\displaystyle{ n+1}\) powstaje przez "dopisanie" do wyniku bez serii po \(\displaystyle{ 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 \(\displaystyle{ n+1}\). rzucie tego samego wyniku cząstkowego, co w \(\displaystyle{ n}\). rzucie.
Mamy więc taki układzik:
\(\displaystyle{ \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 \(\displaystyle{ x_n=2b_n-b_{n+1}}\)
otrzymujemy
\(\displaystyle{ x_{n+1}=b_{n+1}-b_n}\), stąd dla \(\displaystyle{ n \ge 2}\) jest \(\displaystyle{ x_n=b_n-b_{n-1}}\)
i ostatecznie \(\displaystyle{ 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 \(\displaystyle{ b_1=2, b_2=4}\)
