Rappresentazione tramite Fibonacci
Rappresentazione tramite Fibonacci
Dimostrare che ogni numero naturale a è esprimibile IN MODO UNICO nella forma
$ a = F_{n_1} + F_{n_2} + \ldots + F_{n_m} $ dove
$ 1 \le m $, $ n_j \le n_{j-1} - 2 $ per ogni $ j = 1, 2, \ldots, m $, e $ n_m > 1 $.
e dove $ F_k $ è il k-esimo numero di Fibonacci (si intende $ F_1 = 1, F_2 = 1, F_3 = 2, \ldots $)
Il fatto che sia esprimibile non è molto problematico, l'unicità della rappresentazione invece un po' di più. Buon lavoro
$ a = F_{n_1} + F_{n_2} + \ldots + F_{n_m} $ dove
$ 1 \le m $, $ n_j \le n_{j-1} - 2 $ per ogni $ j = 1, 2, \ldots, m $, e $ n_m > 1 $.
e dove $ F_k $ è il k-esimo numero di Fibonacci (si intende $ F_1 = 1, F_2 = 1, F_3 = 2, \ldots $)
Il fatto che sia esprimibile non è molto problematico, l'unicità della rappresentazione invece un po' di più. Buon lavoro
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
Forse ho capito male, ma questo problema non è per nulla tecnico... se sono riuscito a risolverlo io significa anzi che è molto alla portata di un risolutore di livello medio-basso come me (l'ho preso dal LeVeque).Jordan ha scritto:Una generalizzazione di questo fatto era stata proposta per l'oliforum contest da Darij Gringberg, poi abbiamo optato per qualcosa di meno tecnico ^^
O il "tecnico" si riferisce solo alla generalizzazione?
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
Ti confermo che questo problema non è affatto tecnico Penso si riferisca alla generalizzazione.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Se non mi sbaglio è l'ultima voce dell'indice analitico. E sulla pagina di Wikipedia (inglese) di questo celebrato teorema c'è anche questo fatterello carino che vi invito a provare:
One can define the following operation $ a\circ b $ on natural numbers ''a'', ''b'': given the Zeckendorf representations
$ a=\sum_{i=0}^kF_{c_i}\;(c_i\ge2) $ and $ b=\sum_{j=0}^lF_{d_j}\;(d_j\ge2) $ we define the '''Fibonacci product''' $ a\circ b=\sum_{i=0}^k\sum_{j=0}^lF_{c_i+d_j}. $
For example, the Zeckendorf representation of 2 is F_3, and the Zeckendorf representation of 4 is F_4 + F_2 (F_1 is disallowed from representations), so $ 2 \circ 4 = F_{3+4} + F_{3+2} = 13 + 5 = 18. $
Donald Knuth proved the surprising fact that this operation is associative.
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Esattamente; il tecnico si riferiva alla generalizzazione, si.. per quest'ultima (vi prego di non divulgarla almeno per adesso):fph ha scritto:Sull'Engel il risultato è noto con il divertente nome di lemma di Zeckendorf.
"Sia $ t \in \mathbb{N} $ fissato e sia fissato $ T=\{a_1,a_2,\ldots,a_t\}\subseteq \mathbb{Z} $; inoltre un insieme $ S \subseteq \mathbb{Z} $ è detto buono se $ s \in S $ implica $ s+1 \not \in S $. Sapendo che vale l'identità $ \displaystyle \sum_{s \in S}{f_{n+s}}=\sum_{a_i \in T}{f_{n+a_i}} $ per ogni intero n sufficientemente grande, mostrare che un insieme S buono esiste ed è unico."
The only goal of science is the honor of the human spirit.
Uhm... Jordan con grandi sforzi penso di essere riuscito a risolvere la generalizzazione. Non è particolarmente tecnica, l'unico fatto non elementare che ho usato è:
Definito [x] l'intero più vicino a x vale:
$ $[\phi F_n]=F_{n+1} $
Non scrivo la dimostrazione un po' perchè è lunghetta, un po perchè hai detto di non divulgare quindi presumo che la soluzione sia meglio non postarla.
Definito [x] l'intero più vicino a x vale:
$ $[\phi F_n]=F_{n+1} $
Non scrivo la dimostrazione un po' perchè è lunghetta, un po perchè hai detto di non divulgare quindi presumo che la soluzione sia meglio non postarla.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai