[MIX] Kilka zadanek

[justynian]

3.

Niestety chyba nie ma ładnego wyniku i też nie zamierzam tego rozwiązania doprowadzić do końcowego wyniku.

Ukryta treść:    

Liczba świeżaków (nowo narodzonych licealistów) po \(\displaystyle{ n}\) miesiącach wyraża się wzorem:

\(\displaystyle{ a_n=4a_{n-2}+6a_{n-3}+6a_{n-4}+6a_{n-5}+6a_{n-6}.}\)

Warunki początkowe w zadaniu to \(\displaystyle{ a_0=1, a_{-1}=0, a_{-2}=0,\ldots}\)

Zatem w celu rozwiązania zadania należy znaleźć wszystkie rozwiązania \(\displaystyle{ x_1,x_2,x_3,x_4,x_5,x_6}\) równania

\(\displaystyle{ x^6-4x^4-6x^3-6x^2-6x-6=0}\).

Wolfram alpha twierdzi że cztery z nich będą zespolone. W ogólności te rozwiązania nie muszą wyrażać się przez pierwiastniki. Nie wiem jak jest w tym przypadku.

Wynik będzie postaci
\(\displaystyle{ a_n=C_1x_1^n+\ldots+C_6x_6^n}\),

gdzie \(\displaystyle{ C_k}\) to stałe, jakie należy dobrać na podstawie warunków początkowych.

Liczba licealistów po \(\displaystyle{ n}\) miesiącach to \(\displaystyle{ a_n+a_{n-1}+\ldots+a_{n-5}}\)

-- 8 kwi 2011, o 16:13 --

Oczywiście z tego co napisałem nie wynika, że nie istnieje ładne rozwiązanie do 3, więc może jeszcze ktoś coś wymyśli.

No niestety jest źle zapomniałeś w rekurencji o tym że są jeszcze organizmy żywe z poprzedniej partii oraz o tym że niektóre umierają...

[norwimaj]

każdy licealista umiera po wydaniu 28 potomków.

Czy należy to rozumieć dosłownie? Ja przyjąłem niedosłowną interpretację, że umiera po wydaniu 28 bezpośrednich potomków.

W przypadku dosłownej interpretacji każdy licealista umiera po czterech miesiącach zamiast po sześciu. I równanie na liczbę świeżaków należałoby zastąpić równaniem.

\(\displaystyle{ a_n=4a_{n-2}+6a_{n-3}+6a_{n-4}}\).

W przypadku jeszcze dosłowniejszej interpretacji treści zadania licealista rodzi nowe licealisty też po swojej śmierci, ale wątpię w to, aby autorowi o to chodziło.

zapomniałeś w rekurencji o tym że są jeszcze organizmy żywe z poprzedniej partii

Nie zgadzam się z zarzutem. Może nie wyraziłem się najzręczniej, ale napisałem, że

Liczba licealistów po \(\displaystyle{ n}\) miesiącach to \(\displaystyle{ a_n+a_{n-1}+\ldots+a_{n-5}}\)

czyli odpowiedzią do zadania nie jest \(\displaystyle{ a_n}\). Ciąg \(\displaystyle{ a_n}\) oznacza tylko liczbę nowo narodzonych licealistów a nie wszystkich.

oraz o tym że niektóre umierają...

Gdzie o tym zapomniałem?

[justynian]

czyli odpowiedzią do zadania nie jest \(\displaystyle{ a_n}\). Ciąg \(\displaystyle{ a_n}\) oznacza tylko liczbę nowo narodzonych licealistów a nie wszystkich.

To rzeczywiści broni twego rozwiązania chodź właśnie tym wprowadziłeś mnie w błąd, niemniej ostatecznego rozwiązania nie wyznaczyłeś zapewne ze względu na kłopotliwą metodę bo zliczanie tych wszystkich nowaków jest ciekawe i żmudne... Przyjęcie jako a_n liczby licealistów po n miesiącach i napisanie nowej rekurencji daje rozwiązanie bez takiej złożoności.

[norwimaj]

Moim zdaniem oba ciągi spełniają tę samą rekurencję.
Niech \(\displaystyle{ a_n}\) to będzie liczba nowo narodzonych licealistów po \(\displaystyle{ n}\) miesiącach, natomiast \(\displaystyle{ b_n}\) to liczba wszystkich licealistów po \(\displaystyle{ n}\) miesiącach.

Wtedy \(\displaystyle{ b_n=a_n+a_{n-1}+\ldots+a_{n-5}}\).

Załóżmy że \(\displaystyle{ a_n}\) spełnia równanie rekurencyjne, które napisałem. Nawet jeśli się w nim pomyliłem, to nie będzie to miało znaczenia dla dalszej części rozumowania.

Mamy:
\(\displaystyle{ a_n=4a_{n-2}+6a_{n-3}+6a_{n-4}+6a_{n-5}+6a_{n-6}}\),
\(\displaystyle{ a_{n-1}=4a_{n-3}+6a_{n-4}+6a_{n-5}+6a_{n-6}+6a_{n-7}}\),
\(\displaystyle{ \ldots}\)
\(\displaystyle{ \ldots}\)
\(\displaystyle{ a_{n-5}=4a_{n-7}+6a_{n-8}+6a_{n-9}+6a_{n-10}+6a_{n-11}}\).

Po dodaniu tych równości stronami otrzymujemy:
\(\displaystyle{ b_n=4b_{n-2}+6b_{n-3}+6b_{n-4}+6b_{n-5}+6b_{n-6}}\).

Teraz zagadka. Dlaczego pomimo że jest ta sama rekurencja, oraz te same warunki dla wyrazów o numerach \(\displaystyle{ 0,-1,-2,-3,\ldots}\), to nie zachodzi tożsamość \(\displaystyle{ a_n=b_n}\)?

Rozwiązanie zagadki:

Ukryta treść:    

Rekurencja dla ciągu \(\displaystyle{ a_n}\) jest prawdziwa, o ile \(\displaystyle{ n\ne0}\). Rekurencja dla ciągu \(\displaystyle{ b_n}\) będzie więc prawdziwa, o ile \(\displaystyle{ n\not\in\{0,1,2,3,4,5\}}\). Nie możemy więc przy wyznaczaniu wyrazu ciągu posłużyć się ujemnymi indeksami.

To teraz postawmy sobie pytanie. Czy nie da się ułożyć prostszej rekurencji dla ciągu \(\displaystyle{ b_n}\). Postaram się uzasadnić, że nie, ale sam nie jestem w pełni przekonany, więc proszę o wskazanie ewentualnej ściemy.

Stw.1 Jeśli jakiś ciąg spełnia dwie rekurencje jednorodne, o stałych współczynnikach, których wielomiany charakterystyczne to \(\displaystyle{ w(x)}\) i \(\displaystyle{ v(x)}\), to spełnia też równanie rekurencyjne o wielomianie charakterystycznym równym \(\displaystyle{ \gcd(w(x),v(x))}\).

Dowód algorytm Euklidesa

Stw.2 Jeśli ciąg \(\displaystyle{ a_n}\) spełnia równanie j.w., to wśród równań rekurencyjnych, które on spełnia, istnieje równanie najmniejsze (w sensie podzielności wielomianów charakterystycznych).

Dowód wniosek z poprzedniego stwierdzenia

Stw.3 Wielomian \(\displaystyle{ w(x)=x^6-4x^4-6x^3-6x^2-6x-6}\) jest nierozkładalny w zbiorze liczb wymiernych.

Dowód Stosujemy kryterium Eisensteina dla \(\displaystyle{ p=2}\).

Stw.4 Nie jest łatwo w zadaniu 3. znaleźć prostą rekurencję.

Dowód Stosujemy stwierdzenie 2 i stwierdzenie 3.

[justynian]

Ciekawe bo nie widzę blefu lecz gdy przyjmiemy za \(\displaystyle{ b_n}\) liczbę licealistów po n miesiącach to mamy:

\(\displaystyle{ b_n=b_{n-1}+4(b_{n-2}-b_{n-3})+6(b_{n-3}-b_{n-6})-b_{n-6}=b_{n-1}+4b_{n-2}+2b_{n-3}-7b_{n-6}}\)
co daje istotnie różną rekurencje.

[norwimaj]

Żebyśmy mieli jasność, to wyjaśnijmy kilka kwestii:

• \(\displaystyle{ b_{n-2}-b_{n-3}}\) to nie jest liczba licealistów w wieku \(\displaystyle{ 2}\) miesięcy. Jest to (liczba licealistów w wieku \(\displaystyle{ 2}\) miesięcy) minus (liczba licealistów, którzy umarli \(\displaystyle{ 2}\) miesiące temu).
• \(\displaystyle{ b_{n-3}-b_{n-6}}\) to nie jest liczba licealistów w wieku od \(\displaystyle{ 3}\) do \(\displaystyle{ 6}\) miesięcy (w tym zmarli).
• \(\displaystyle{ b_{n-6}}\) to nie jest liczba licealistów, którzy ostatnio zmarli. Jest to liczba licealistów, którzy zmarli w ciągu ostatnich \(\displaystyle{ 6}\) miesięcy.

Czy Twój wzór rekurencyjny sformułowałeś na podstawie tych fałszywych stwierdzeń, czy w jakiś inny sposób?

[justynian]

Masz racje moje rozumowanie było błędne, sorki za zamieszanie i dzięki