Gli interi positivi in "base fattoriale"

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Gli interi positivi in "base fattoriale"

Messaggio da HiTLeuLeR » 01 ago 2005, 09:26

Problema: dimostrare che, per ogni $ n\in\mathbb{N}_0 $, esistono univocamente determinati $ k\in\mathbb{N}_0 $ e una sequenza $ a_1, a_2, \ldots, a_k $ di interi tali che $ n = a_1 \cdot 1! + a_2 \cdot 2! + \ldots + a_k \cdot k!\; $, $ a_k \neq 0 $ e $ 0 \leq a_i \leq i $, per ogni $ i = 1, 2, \ldots, k $.

Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor » 03 ago 2005, 11:56

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+1)! $ per un solo $ h\in\mathbb{N}_0 $. Allora deve necessariamente essere $ k=h $.

Se infatti fosse $ k>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 $.

MindFlyer

Messaggio da MindFlyer » 03 ago 2005, 12:05

Una delle domande del mio orale di ammissione SNS!

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 03 ago 2005, 12:36

La tua soluzione è corretta, Igor. Forse esageratamente lunga, ma corretta... :wink: Le buone idee ci sono tutte, in ogni caso, e questo è l'importante! :D

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 03 ago 2005, 12:42

MindFlyer ha scritto:Una delle domande del mio orale di ammissione SNS!
...ma a questo punto siamo tutti curiosi di conoscere anche la *tua* soluzione, Mind! :o

MindFlyer

Messaggio da MindFlyer » 03 ago 2005, 14:43

Beh, penso ci sia un solo modo sensato di risolverlo.
E' sufficiente dire che il più alto numero scrivibile con n cifre è il predecessore del più basso numero scrivibile con n+1 cifre (e questo non è altro che il lemma iniziale di Igor). Detto questo, è ovvio che il nostro sistema di numerazione beccherà ogni naturale una ed una sola volta (una banale induzione!).
Anche se non ho letto completamente la soluzione di Igor, penso che in sostanza dica questa cosa.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 04 ago 2005, 13:19

Th. della divisione: se $ m,n \in\mathbb{N} $, $ n \neq 0 $, esistono univocamente determinati $ q, r \in \mathbb{N} $, con $ 0 \leq r < n $, t.c. $ m = nq + r $.

Aggiungici il fatto che può porsi $ \displaystyle [1, +\infty[ \; = [1!, 2![ \;\cup \;[2!, 3![ \;\cup \ldots \cup \;[n!, (n+1)![\; \cup \ldots $; mescola il tutto con un poco di induzione e... il minestrone è pronto in tavola. Saranno sì e no cinque righe con tutti i dettagli del caso. Vabbè, hai ragione pure tu (retorico): ma in fondo... chissenefrega!? :roll:

Rispondi