szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 11 cze 2019, o 22:08 
Użytkownik

Posty: 671
Niech b _{n} oznacza ilość ciągów długości n utworzonych z liczb 0,1,2
w których występuje nieparzysta liczba zer.
Uzasadnij, że ciąg b _{n} spełnia następującą rekurencję: b _{1} =1 , b _{n+1}=b _{n}+3 ^{n}

Jak to ugryźć?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 11 cze 2019, o 22:34 
Użytkownik
Avatar użytkownika

Posty: 2129
Lokalizacja: hrubielowo
Abo czegoś nie rozumiem albo jest źle. Jak b_1 może być równy 1 skoro są 3 ciągi długości 1 możliwe do utworzenia z \left\{ 0,1,2\right\} są nimi \left\langle 0\right\rangle, \left\langle 1\right\rangle, \left\langle 2\right\rangle. Poza tym dodając ilość ciągów n wyrazowych utworzonych z \left\{ 0,1,2\right\} to 3^n (na każdym miejscu mamy trzy możliwości zatem 3 \cdot 3 \cdot ... \cdot 3 i tak n razy). Taki ciąg nie spełni tej rekurencji 3^{n+1} \neq 3^n+3^n. Raczej b_n=3b_{n-1} i to by się też zgadzało z interpretacją kombinatoryczną gdzie dodanie kolejnego miejsca daje trzy kolejne możliwości.
Góra
Mężczyzna
PostNapisane: 11 cze 2019, o 22:37 
Użytkownik

Posty: 671
Janusz Tracz napisał(a):
Abo czegoś nie rozumiem albo jest źle. Jak b_1 może być równy 1 skoro są 3 ciągi długości 1 możliwe do utworzenia z \left\{ 0,1,2\right\} są nimi \left\langle 0\right\rangle, \left\langle 1\right\rangle, \left\langle 2\right\rangle. Poza tym dodając ilość ciągów n wyrazowych utworzonych z \left\{ 0,1,2\right\} to 3^n (na każdym miejscu mamy trzy możliwości zatem 3 \cdot 3 \cdot ... \cdot 3 i tak n razy). Taki ciąg nie spełni tej rekurencji 3^{n+1} \neq 3^n+3^n. Raczej b_n=3b_{n-1} i to by się też zgadzało z interpretacją kombinatoryczną gdzie dodanie kolejnego miejsca daje trzy kolejne możliwości.

Ale jest warunek, że musi być nieparzysta liczba zer
Góra
Mężczyzna
PostNapisane: 11 cze 2019, o 23:27 
Użytkownik
Avatar użytkownika

Posty: 13885
Lokalizacja: Wrocław
kmarciniak1 napisał(a):
Jak to ugryźć?

Zę-ba-mi! Oh, ba-mi ba-mi, zę-ba-mi, oh, zę-ba-mi, oh, zę… zę-ba-mi, zę-ba mi
https://www.youtube.com/watch?v=hwZNL7QVJjE

Wprowadźmy sobie (tak będzie wygodnie+jestem mało inteligentny, więc nie widzę, jak to ominąć) drugi ciąg (c_n)_{n=1}^{\infty}, gdzie c_n jest liczbą (nie ilością) ciągów długości n o wyrazach ze zbioru \left\{ 0,1,2\right\}, w których występuje parzyście wiele zer. Wówczas oczywiście jest b_n+c_n=3^n. Ponadto nietrudno zauważyć, że
b_{n+1}=2b_n+c_n:
do ciągu długości n z nieparzystą liczbą zer dopisujemy na końcu dwójkę lub jedynkę (dwa sposoby) i dalej jest nieparzyście wiele zer, bądź do ciągu długości n z parzystą liczbą zer dopisujemy na końcu zero, co daje ciąg długości n+1 z nieparzystą liczbą zer.
Na podobnej zasadzie (nie będę tego jak wyżej rozpisywać) jest
c_{n+1}=2c_n+b_n, ale to nam akurat niepotrzebne. ;)

W otrzymanej zależności
b_{n+1}=2b_n+c_n wstawiamy c_n=3^n-b_n i mamy tezę zadania.
Aha, no i b_1=1 to oczywiste raczej…
Góra
Mężczyzna
PostNapisane: 11 cze 2019, o 23:41 
Użytkownik

Posty: 671
Dziękuje bardzo Premislav, za pomysłowe rozwiązanie. :D
W sumie gdy się wprowadzi ten drugi ciąg, problem staje się dużo prostszy. Muszę zapamiętać ten sposób.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rekurencja - 2 zadania  Watari  16
 rekurencja, ilość ciągów  kolegasafeta  1
 Rekurencja, delta mniejsza od zera  combinev2  3
 Prosta rekurencja z funkcją tworzącą  adam-ek  2
 Rekurencja, silnia, ciąg. - zadanie 2  spedeer2007  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl