Pagina 1 di 1

vekkio sant'anna

Inviato: 04 set 2009, 02:05
da lucs223
ecco un vecchio quesito del sant'anna su cui vorrei un aiuto grazie mille

dimostrare che ogni intero positivo può essere scritto ed in modo unico nella forma:

a1*1!+ a2*2!+ a3*3!+ .... +ak*k! con 0<= ai <= i ed ak diverso da zero

Re: vekkio sant'anna

Inviato: 04 set 2009, 02:10
da fede90
lucs223 ha scritto:ecco un vecchio quesito del sant'anna su cui vorrei un aiuto grazie mille

dimostrare che ogni intero positivo può essere scritto ed in modo unico nella forma:

$ a_1\cdot 1!+ a_2\cdot 2!+ a_3\cdot 3!+ \dots +a_k\cdot k! \ , \quad 0\leq a_i \leq i \ , \quad a_k\neq 0 $

Inviato: 04 set 2009, 03:45
da jordan
Da qui:
Igor ha scritto:Lemma

$ 1*1!+2*2!+\ldots +n*n!=(n+1)!-1 $

Si dimostra facilmente per induzione.

Ammettiamo ora che,fissato $ n $,esistano $ k\in\mathbb{N}_0 $ e una sequenza di interi $ a_1,a_2,\ldots ,a_k $ tali che $ n=a_1*1!+a_2*2!+\ldots +a_k*k! $,$ a_k\neq 0 $ e $ 0\leq a_1\leq i $ per ogni $ i=1,2,\ldots ,k $.Dimostriamo che sono gli unici a verificare queste condizioni.

Verifichiamo dapprima che $ k $ è determinato univocamente.

Per ogni $ n $ vale infatti $ h!\leq n<h>h $, avremo che il termine $ a_k*k! $ vale almeno $ (h+1)! $, in contrasto con l'ipotesi $ n<(h+1)! $.
Se invece fosse $ k<h $, avremo che $ n $ vale al massimo $ 1*1!+2*2!+\ldots +(h-1)*(h-1)!=h!-1 $, in contrasto con l'ipotesi $ n\geq h! $.

Dimostriamo ora che $ a_k $ è univocamente determinato.Ammettiamo infatti che esista un'altra sequenza di interi $ b_1,b_2,\ldots ,b_k $, con $ b_k\neq a_k $ che verifica le condizioni poste.Avremo allora che

$ n=a_1*1!+a_2*2!+\ldots +a_k*k! $

$ n=b_1*1!+b_2*2!+\ldots +b_k*k! $

Sottraendo membro a membro le due equazioni, troviamo

$ (a_k-b_k)*k!=(b_1-a_1)*1!+\ldots +(b_{k-1}-a_{k-1})(k-1)! $

Il membro di sinistra vale almeno $ k! $, mentre il membro di destra vale al massimo $ 1*1!+2*2!+\ldots +(k-1)*(k-1)!=k!-1 $.Abbiamo trovato un assurdo: possiamo dunque concludere che $ a_k $ è univocamente determinato.

Ora dimostriamo che, se per un certo $ i=1,2,\ldots ,k-1 $ le cifre $ a_{i+1},a_{i+2},\ldots ,a_k $ sono univocamente determinate, anche la cifra $ a_i $ lo è.
Ammettiamo dunque che esista un'altra sequenza di interi $ b_1,b_2,\ldots ,b_k $, con $ b_{i+1}=a_{i+1},\ldots ,b_k=a_k $, $ b_i\neq a_i $ che verifichi la condizioni poste.Avremo allora che

$ n=a_1*1!+a_2*2!+\ldots +a_k*k! $

$ n=b_1*1!+b_2*2!+\ldots +b_k*k! $

Sottraendo membro a membro troviamo

$ (a_i-b_i)*i!=(b_1-a_1)*1!+\ldots +(b_{i-1}-a_{i-1})(i-1)! $

Abbiamo già visto che questa equazione conduce ad un'assurdo, dunque $ a_i $ è determinato univocamente.

Ora, poichè $ a_k $ è determinato in maniera univoca, tutti gli $ a_i $ lo sono.

Resta ora da dimostrare che per ogni $ n\in\mathbb{N}_0 $ esistono effettivamente $ k\in\mathbb{N}_0 $ e una sequenza di interi $ a_1,a_2,\ldots ,a_k $ tali che $ n=a_1*1!+a_2*2!+\ldots+a_k*k! $,$ a_k\neq 0 $ e $ 0\leq a_1\leq i $ per ogni $ i=1,2,\ldots ,k $.

Ammettiamo che,fissato un certo $ h\in\mathbb{N}_0 $,per ogni $ 1\leq n\leq h!-1 $ esistano $ k\in\mathbb{N}_0 $ e una sequenza di interi$ a_1,a_2,\ldots ,a_k $ che verificano le condizioni poste.Avremo in questo caso $ k\leq h-1 $.
Dimostriamo ora che anche per gli $ h!\leq n\leq (h+1)!-1 $ esistono $ k\in\mathbb{N}_0 $ e una sequenza di interi $ a_1,a_2,\ldots ,a_k $che verificano le condizioni poste.Abbiamo già visto che per questi $ n $ si ha $ k=h $.Inoltre esiste univocamente determinato un $ \omega\in 1,2,\ldots h $ tale che $ \omega h!\leq n<(\omega +1)h! $.Se poniamo $ a_k=\omega $ troviamo

$ n=a_1*1!+\ldots +a_{h-1}*(h-1)!+\omega*h! $

$ a_1*1!+\ldots +a_{h-1}*(h-1)!=n-\omega*h! $

Il membro di destra di questa equazione è compreso tra $ 0 $ e $ h!-1 $
Ma per le ipotesi fatte, per ogni numero di questa forma esistono $ k\in\mathbb{N}_0 $, con $ k\leq h-1 $, e una sequenza di interi $ a_1,a_2,\ldots ,a_k $ che verificano le condizioni poste.Allora lo stesso vale anche per $ n $.Basta infatti prendere la sequenza $ a_1,a_2,\ldots ,a_m $ che genera $ n-\omega*h! $, porre $ a_h=\omega $, e porre uguali a zero gli eventuali $ a_i $ tali che $ m<i<h $, per trovare la sequenza che genera $ n $.Nel caso in cui $ n-\omega*h!=0 $, basta porre $ a_h=\omega $ e tutti gli altri $ a_i $ uguali a zero.

Ora, poichè per i numeri da $ 1 $ a $ 2!-1=1 $ esistono $ k\in\mathbb{N}_0 $ e una sequenza di interi $ a_1,a_2,\ldots ,a_k $ tali che $ n=a_1*1!+a_2*2!+\ldots +a_k*k! $,$ a_k\neq 0 $ e $ 0\leq a_1\leq i $ per ogni $ i=1,2,\ldots ,k $,per induzione lo stesso vale per tutti gli $ n\in\mathbb{N}_0 $.

Inviato: 04 set 2009, 04:20
da Tibor Gallai
Omg. Come si fa a scrivere una paginata di roba dopo un lemma equivalente alla tesi? Per di più, la dimostrazione del lemma è pure omessa...
Qualunque cosa abbia scritto Igor in quel mare di formule (che per quanto ne so potrebbero anche valergli la medaglia Fields, non ho intenzione di leggerle), credo che dopo il lemma si possa mettere direttamente un corollario con la tesi del problema, ed una dimostrazione di 2 righe.

Inviato: 04 set 2009, 04:24
da jordan
Se guardi bene al sesto rigo credo che il messaggio si sia mangiato anche una parte :lol: