Pagina 1 di 1
Rappresentazione tramite Fibonacci
Inviato: 19 mar 2010, 19:13
da Gauss91
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
Inviato: 19 mar 2010, 20:27
da jordan
Una generalizzazione di questo fatto era stata proposta per l'oliforum contest da Darij Gringberg, poi abbiamo optato per qualcosa di meno tecnico ^^
Inviato: 19 mar 2010, 21:32
da dario2994
Jordan puoi scrivere la generalizzazione che sono curioso...
Inviato: 19 mar 2010, 21:57
da Gauss91
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 ^^
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).
O il "tecnico" si riferisce solo alla generalizzazione?
Inviato: 19 mar 2010, 22:04
da dario2994
Ti confermo che questo problema non è affatto tecnico
Penso si riferisca alla generalizzazione.
Inviato: 19 mar 2010, 23:36
da fph
Sull'Engel il risultato è noto con il divertente nome di lemma di Zeckendorf.
Inviato: 19 mar 2010, 23:46
da Gauss91
[quote=fph]Sull'Engel il risultato è noto con il divertente nome di lemma di Zeckendorf.[/quote]
Ah! Non l'avevo visto! Bene non si finisce mai di imparare!
Inviato: 20 mar 2010, 01:04
da fph
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.
Inviato: 20 mar 2010, 03:42
da jordan
fph ha scritto:Sull'Engel il risultato è noto con il divertente nome di lemma di Zeckendorf.
Esattamente; il tecnico si riferiva alla generalizzazione, si.. per quest'ultima (vi prego di non divulgarla almeno per adesso):
"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."
Inviato: 22 mar 2010, 13:02
da dario2994
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.
Inviato: 22 mar 2010, 13:15
da jordan
Si, ci hai preso ^^
E ti ringrazio per non averla postata