szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: ilość funkcji
PostNapisane: 3 kwi 2016, o 18:38 
Użytkownik

Posty: 277
Lokalizacja: warszawa
Niech n \geq 2 naturalne. Oblicz ile jest funkcji f: \{ 1,2,...,n \} \rightarrow \{ 1,2,3,4,5 \} takich ze |f(k+1)-f(k)| \geq 3 dla k=1,2,...,n-1.
Góra
Mężczyzna Offline
 Tytuł: ilość funkcji
PostNapisane: 4 kwi 2016, o 14:40 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
W tym zadaniu rządzi ciąg Fibonacciego.
Można to pokazać.

Zauważmy, że:

f(1), f(2),f(3),f(4),f(5),...

Mogą zgodnie z warunkiem zadania przyjmować wartości takie:

\left\{ 1,4\right\}

\left\{ 2,5\right\}

\left\{ 1,5\right\}

Jak widać nie może wystąpić trójka.

załóżmy, że:

f(1)=4, nasze a(0)

wtedy f(2)=1, nasze a(1)

ale dalej:

f(3) musi być równe tylko i wyłącznie: 4 \vee 5 nasze a(2)

co w drugim rzucie daje już dwie możliwości

dalejf(4)=1, f(4)=2 \vee 1 - trzy możliwości, nasze a(3)


dalejf(5)=4 \vee 5, f(5)=5 ,f(5)= 4 \vee 5 -pięć możliwości, nasze a(4)

można iść dalej ale łatwo zauważyć, że:

a(n+2)=a(n+1)+a(n)

tu zrobiłem dla przykładu gdzie 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ć

Obrazek

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

Co też widać z obrazka.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość różnowartościowych niemonotonicznych funkcji.  Anonymous  2
 Pojemniki z kulami-ilość sposobów rozmieszczenia kul.  qwertyyyy  2
 Ilość elementów w zbiorze-zadanie.  Anonymous  2
 Ilość suriekcji zbioru k-elementowego na n-elementowy  DEXiu  2
 Ilość różnych wyrazów o długości n z zastrzeżeniem  apacz  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl