Gli interi positivi in "base fattoriale"
Gli interi positivi in "base fattoriale"
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 $.
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 $.
$ 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 $.
Le buone idee ci sono tutte, in ogni caso, e questo è l'importante! 
-
MindFlyer
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.
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.
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
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!?