ilość funkcji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
alfred0
Użytkownik
Użytkownik
Posty: 276
Rejestracja: 7 cze 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 38 razy

ilość funkcji

Post autor: alfred0 »

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.}\)
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

ilość funkcji

Post autor: arek1357 »

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ć

Kod: Zaznacz cały

https://imageshack.com/i/po5qK7z8j
AU
AU
5qK7z8.jpg (12.53 KiB) Przejrzano 58 razy
[/url]

analogicznie będzie jeśli \(\displaystyle{ f(1)=1 \vee 2 \vee 5}\)

Co też widać z obrazka.
ODPOWIEDZ