Determinare quante sono le funzioni f:{1,...,n} --> {1,...,5} tali che $ |f(i+1)-f(i)| \ge 3 $ per i =1,...,n-1.
Provenienza: Cortona 2001.
Buon lavoro, Simone.
Funzioni quasi Fibonacciose
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Riesumando quà e là
Tanto per riesumare un vecchi post azzardo una soluzione a questo problema. Tento di farla utilizzando una divisione in step (anche se il problema non ne necessita ma almeno mi alleno)... non l'ho mai fatto quindi potrebbe non capirsi una mazza:
Step 0 Definizioni utili
Definisco $ f_n(k) $ come la funzione f(k) con k che va da 1 a n.
Definisco $ C(n) $ il numero delle possibili funzioni $ f_n(k) $
Step 1 Collegare il valore di f(i+1) a quello di f(i)
Sostituendo f(i) con {1,2,3,4,5} nell'espressione
$ |f(i+1)-{1,2,3,4,5}|\ge 3 $
Si trova che i valori di f(i+1) sono in relazione con quelli di f(i) secondo questa regola:
$ f(i)\rightarrow f(i+1) $
$ 1\rightarrow \{4,5\} $
$ 2\rightarrow 5 $
$ 3\rightarrow Assurdo $
$ 4\rightarrow 1 $
$ 5\rightarrow \{1,2\} $
Si ricava perciò che il valore 3 può comparire solo in $ f_1(1) $ e perciò $ C(1)=5 $
Step 2 Proprietà notevoli delle funzioni
La funzione C(k)ha queste caratteristiche:
a) C(2)=6 (per prove)
b) C(3)=10 (per prove)
c) C(n)=C(n-1)+C(n-2) per n>3. Per dimostrare questo lemma prima di tutto osservo che $ C(n)=C(n\ con\ f(n)=\{1,5\})+C(n\ con\ f(n)=\{2,4\}) $.
Ora dimostro che $ C(n\ con\ f(n)=\{1,5\})=C(n-1) $: basta notare che i primi n-1 valori restituiti da $ f_n(k) $ corrispondono alle possibili funzioni $ f_{n-1}(k) $ e l'ultimo valore è costretto dato che f(n), conoscendo f(n-1), può essere o 1 o 5 ma non entrambi.
Ora dimostro che $ C(n\ con\ f(n)=\{2,4\})=C(n-2) $: questo perchè se f(n)={2,4} allora f(n-1)={1,5}; ma per dimostrazione precedente $ C(n-1\ con\ f_{n-1}(n-1)=\{1,5\})=C(n-2) $ da cui la tesi.
Step 3 Conclusione
Per quanto analizzato nello step precedente C(1)=5;C(2)=6;C(3)=10 e per n>3 C(n)=C(n-1)+C(n-2), da qui posso dimostrare che per n>3 $ C(n)=2\cdot F(n+2) $ con F(n) l'nEsimo numero di Fibonacci. Lo dimostro per induzione:
Per n=4 è vero. Per n=5 è vero. Se è vero per n-2 e per n-1 allora $ C(n)=2\cdot F(n+1)+2\cdot F(n)=2\cdot (F(n+1)+F(n))=2\cdot F(n+2) $ da cui la tesi.
Spero di non aver fatto troppi casini, sopratutto perchè per scrivere in modo decente la dimostrazione ho impiegato almeno 1 ora e mezza xD
Step 0 Definizioni utili
Definisco $ f_n(k) $ come la funzione f(k) con k che va da 1 a n.
Definisco $ C(n) $ il numero delle possibili funzioni $ f_n(k) $
Step 1 Collegare il valore di f(i+1) a quello di f(i)
Sostituendo f(i) con {1,2,3,4,5} nell'espressione
$ |f(i+1)-{1,2,3,4,5}|\ge 3 $
Si trova che i valori di f(i+1) sono in relazione con quelli di f(i) secondo questa regola:
$ f(i)\rightarrow f(i+1) $
$ 1\rightarrow \{4,5\} $
$ 2\rightarrow 5 $
$ 3\rightarrow Assurdo $
$ 4\rightarrow 1 $
$ 5\rightarrow \{1,2\} $
Si ricava perciò che il valore 3 può comparire solo in $ f_1(1) $ e perciò $ C(1)=5 $
Step 2 Proprietà notevoli delle funzioni
La funzione C(k)ha queste caratteristiche:
a) C(2)=6 (per prove)
b) C(3)=10 (per prove)
c) C(n)=C(n-1)+C(n-2) per n>3. Per dimostrare questo lemma prima di tutto osservo che $ C(n)=C(n\ con\ f(n)=\{1,5\})+C(n\ con\ f(n)=\{2,4\}) $.
Ora dimostro che $ C(n\ con\ f(n)=\{1,5\})=C(n-1) $: basta notare che i primi n-1 valori restituiti da $ f_n(k) $ corrispondono alle possibili funzioni $ f_{n-1}(k) $ e l'ultimo valore è costretto dato che f(n), conoscendo f(n-1), può essere o 1 o 5 ma non entrambi.
Ora dimostro che $ C(n\ con\ f(n)=\{2,4\})=C(n-2) $: questo perchè se f(n)={2,4} allora f(n-1)={1,5}; ma per dimostrazione precedente $ C(n-1\ con\ f_{n-1}(n-1)=\{1,5\})=C(n-2) $ da cui la tesi.
Step 3 Conclusione
Per quanto analizzato nello step precedente C(1)=5;C(2)=6;C(3)=10 e per n>3 C(n)=C(n-1)+C(n-2), da qui posso dimostrare che per n>3 $ C(n)=2\cdot F(n+2) $ con F(n) l'nEsimo numero di Fibonacci. Lo dimostro per induzione:
Per n=4 è vero. Per n=5 è vero. Se è vero per n-2 e per n-1 allora $ C(n)=2\cdot F(n+1)+2\cdot F(n)=2\cdot (F(n+1)+F(n))=2\cdot F(n+2) $ da cui la tesi.
Spero di non aver fatto troppi casini, sopratutto perchè per scrivere in modo decente la dimostrazione ho impiegato almeno 1 ora e mezza xD
Ultima modifica di dario2994 il 24 mag 2009, 19:37, modificato 1 volta in totale.
Re: Riesumando quà e là
nn è il contrario?dario2994 ha scritto: $ 1\rightarrow \{1,2\} $
$ 5\rightarrow \{4,5\} $
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
Jordan e Skz dove li metti?dario2994 ha scritto:Il problema è solo uno... "qualcuno + esperto" sta al Preimo (e ci rimane per una settimana).
Quindi non è un problema, se hai critiche o hai trovato qualcosa che non va dillo
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!