ilość funkcji
-
- Użytkownik
- Posty: 276
- Rejestracja: 7 cze 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: warszawa
- Podziękował: 38 razy
ilość funkcji
Niech \(\displaystyle{ n \geq 2}\) naturalne. Oblicz ile jest funkcji \(\displaystyle{ f: \{ 1,2,...,n \} \rightarrow \{ 1,2,3,4,5 \}}\) takich ze \(\displaystyle{ |f(k+1)-f(k)| \geq 3}\) dla \(\displaystyle{ k=1,2,...,n-1.}\)
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
ilość funkcji
W tym zadaniu rządzi ciąg Fibonacciego.
Można to pokazać.
Zauważmy, że:
\(\displaystyle{ f(1), f(2),f(3),f(4),f(5)}\),...
Mogą zgodnie z warunkiem zadania przyjmować wartości takie:
\(\displaystyle{ \left\{ 1,4\right\}}\)
\(\displaystyle{ \left\{ 2,5\right\}}\)
\(\displaystyle{ \left\{ 1,5\right\}}\)
Jak widać nie może wystąpić trójka.
załóżmy, że:
\(\displaystyle{ f(1)=4}\), nasze \(\displaystyle{ a(0)}\)
wtedy \(\displaystyle{ f(2)=1}\), nasze \(\displaystyle{ a(1)}\)
ale dalej:
\(\displaystyle{ f(3)}\) musi być równe tylko i wyłącznie: \(\displaystyle{ 4 \vee 5}\) nasze \(\displaystyle{ a(2)}\)
co w drugim rzucie daje już dwie możliwości
dalej\(\displaystyle{ f(4)=1, f(4)=2 \vee 1}\) - trzy możliwości, nasze \(\displaystyle{ a(3)}\)
dalej\(\displaystyle{ f(5)=4 \vee 5, f(5)=5 ,f(5)= 4 \vee 5}\) -pięć możliwości, nasze \(\displaystyle{ a(4)}\)
można iść dalej ale łatwo zauważyć, że:
\(\displaystyle{ a(n+2)=a(n+1)+a(n)}\)
tu zrobiłem dla przykładu gdzie \(\displaystyle{ f(1)=4}\)
pozostałe robi się analogicznie i też wychodzi ciąg Fibonacciego...
Jeśli mało jasne to pisać.
Zadanie powiem ciekawe w rozwiązaniu bo nie spodziewałem się takiego wyniku...
A tu drzewko zadania na którym dobrze już wszystko widać
[/url]
analogicznie będzie jeśli \(\displaystyle{ f(1)=1 \vee 2 \vee 5}\)
Co też widać z obrazka.
Można to pokazać.
Zauważmy, że:
\(\displaystyle{ f(1), f(2),f(3),f(4),f(5)}\),...
Mogą zgodnie z warunkiem zadania przyjmować wartości takie:
\(\displaystyle{ \left\{ 1,4\right\}}\)
\(\displaystyle{ \left\{ 2,5\right\}}\)
\(\displaystyle{ \left\{ 1,5\right\}}\)
Jak widać nie może wystąpić trójka.
załóżmy, że:
\(\displaystyle{ f(1)=4}\), nasze \(\displaystyle{ a(0)}\)
wtedy \(\displaystyle{ f(2)=1}\), nasze \(\displaystyle{ a(1)}\)
ale dalej:
\(\displaystyle{ f(3)}\) musi być równe tylko i wyłącznie: \(\displaystyle{ 4 \vee 5}\) nasze \(\displaystyle{ a(2)}\)
co w drugim rzucie daje już dwie możliwości
dalej\(\displaystyle{ f(4)=1, f(4)=2 \vee 1}\) - trzy możliwości, nasze \(\displaystyle{ a(3)}\)
dalej\(\displaystyle{ f(5)=4 \vee 5, f(5)=5 ,f(5)= 4 \vee 5}\) -pięć możliwości, nasze \(\displaystyle{ a(4)}\)
można iść dalej ale łatwo zauważyć, że:
\(\displaystyle{ a(n+2)=a(n+1)+a(n)}\)
tu zrobiłem dla przykładu gdzie \(\displaystyle{ f(1)=4}\)
pozostałe robi się analogicznie i też wychodzi ciąg Fibonacciego...
Jeśli mało jasne to pisać.
Zadanie powiem ciekawe w rozwiązaniu bo nie spodziewałem się takiego wyniku...
A tu drzewko zadania na którym dobrze już wszystko widać
Kod: Zaznacz cały
https://imageshack.com/i/po5qK7z8j
analogicznie będzie jeśli \(\displaystyle{ f(1)=1 \vee 2 \vee 5}\)
Co też widać z obrazka.