OliForum Matematico

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.

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

dario2994 ha scritto: $ 1\rightarrow \{1,2\} $
$ 5\rightarrow \{4,5\} $

nn è il contrario?

Editato e corretto :)
Per il resto funge?

forse è meglio che lasci la correzione a qualcuno + esperto.... non vorrei scrivere cose sbagliate che poi magari confondono solo le idee

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 ;)

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

Jordan e Skz dove li metti?

Intendevo che molti dei maggiori utenti del forum non ci sono... non che non c'è nessuno ;)
Comunque continuo a consigliarti di esporre i tuoi dubbi se ne hai ;) Mica ti bastono se è una cazzata... anzi può essere utile vedere i propri e gli altrui errori :)