Dimostrare che ogni numero naturale $n$ può essere scritto (e in modo unico) nella forma:
$a_1\cdot 1!+a_2\cdot 2!+a_3\cdot 3!+...+a_k\cdot k!$
Con $0\leq a_i \leq i$
Fattoriali $\rightarrow$ Naturali!
Fattoriali $\rightarrow$ Naturali!
Ἀγεωμέτρητος μηδεὶς εἰσίτω
Re: Fattoriali $\rightarrow$ Naturali!
Considero il numero $n_2$.
Ora eseguo questo algoritmo:
-divido $n_2$ per $2$
-ottengo $n_3$ con resto $r_3$; divido $n_3$ per 3;
-ottengo $n_4$ con resto $r_4$; ...
-...
-arrivo fino a quando $n_k<k$
-a questo punto scrivo il numero come $n_k(k-1)!+\sum_{i=3}^{k}r_i(i-2)!$
-ora, il numero $\sum_{i=3}^{k}r_i(i-2)!$ sappiamo di certo che è minore di $(k-1)!$ (lo si può dimostrare per induzione, ponendo $r_i=i-2$, che è il massimo valore che può assumere); quindi possiamo applicare lo stesso algoritmo anche su tale numero, sapendo che non usufruirà dei termini con i fattoriali maggiori o uguali a $(k-1)$.
Questo algoritmo è in grado, dunque, di fornirci sempre la scomposizione del numero nella configurazione considerata.
Per dimostrare l'unicità, mi basta dire che $k!$ è strettamente maggiore di $\sum_{i=1}^{k-1}i\cdot(i!)$, e $k\cdot(k!)$ è strettamente minore di $(k+1)!$ (la seconda è ovvia, la prima è uguale a quella che ho detto prima che si può dimostrare per induzione); quindi se dall'algoritmo salta fuori che devo considerare il termine $k!$, lo dovrò considerare per forza, e così per tutti gli altri termini. Quindi la scomposizione è unica.
Spero di non aver fatto confusione con gli indici (cosa improbabile :p)
Da dove era?
Ora eseguo questo algoritmo:
-divido $n_2$ per $2$
-ottengo $n_3$ con resto $r_3$; divido $n_3$ per 3;
-ottengo $n_4$ con resto $r_4$; ...
-...
-arrivo fino a quando $n_k<k$
-a questo punto scrivo il numero come $n_k(k-1)!+\sum_{i=3}^{k}r_i(i-2)!$
-ora, il numero $\sum_{i=3}^{k}r_i(i-2)!$ sappiamo di certo che è minore di $(k-1)!$ (lo si può dimostrare per induzione, ponendo $r_i=i-2$, che è il massimo valore che può assumere); quindi possiamo applicare lo stesso algoritmo anche su tale numero, sapendo che non usufruirà dei termini con i fattoriali maggiori o uguali a $(k-1)$.
Questo algoritmo è in grado, dunque, di fornirci sempre la scomposizione del numero nella configurazione considerata.
Per dimostrare l'unicità, mi basta dire che $k!$ è strettamente maggiore di $\sum_{i=1}^{k-1}i\cdot(i!)$, e $k\cdot(k!)$ è strettamente minore di $(k+1)!$ (la seconda è ovvia, la prima è uguale a quella che ho detto prima che si può dimostrare per induzione); quindi se dall'algoritmo salta fuori che devo considerare il termine $k!$, lo dovrò considerare per forza, e così per tutti gli altri termini. Quindi la scomposizione è unica.
Spero di non aver fatto confusione con gli indici (cosa improbabile :p)
Da dove era?
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]
Re: Fattoriali $\rightarrow$ Naturali!
Metto pure la mia.
Fissato k, il numero più grande che posso ottenere è $ \sum_{i=1}^{k}i\cdot i!=(k+1)!-1 $. In più ho $ 2\cdot 3\cdot \dots \cdot (k+1)=(k+1)! $ scelte dei coefficienti, quindi ho al massimo $ (k+1)! $ rappresentazioni. Inoltre se ho anche un $a_h>0$ per un qualche $h>k$ non potrò ottenere un numero minore di $ (k+1)! $, quindi mi basta dimostrare che ogni numero ha al più una rappresentazione e ho finito.
Questo è facile, infatti se un certo n si può scrivere in due modi diversi, sia j il più piccolo intero tale che $ a_j $ è distinto nelle due rappresentazioni, allora ho un assurdo modulo $ (j+1)! $
Fissato k, il numero più grande che posso ottenere è $ \sum_{i=1}^{k}i\cdot i!=(k+1)!-1 $. In più ho $ 2\cdot 3\cdot \dots \cdot (k+1)=(k+1)! $ scelte dei coefficienti, quindi ho al massimo $ (k+1)! $ rappresentazioni. Inoltre se ho anche un $a_h>0$ per un qualche $h>k$ non potrò ottenere un numero minore di $ (k+1)! $, quindi mi basta dimostrare che ogni numero ha al più una rappresentazione e ho finito.
Questo è facile, infatti se un certo n si può scrivere in due modi diversi, sia j il più piccolo intero tale che $ a_j $ è distinto nelle due rappresentazioni, allora ho un assurdo modulo $ (j+1)! $
Re: Fattoriali $\rightarrow$ Naturali!
Era da un test di ammissione al Sant'Anna per Ingegneria!
Ἀγεωμέτρητος μηδεὶς εἰσίτω
Re: Fattoriali $\rightarrow$ Naturali!
sicuro?LukasEta ha scritto:Era da un test di ammissione al Sant'Anna per Ingegneria!
Re: Fattoriali $\rightarrow$ Naturali!
era ben più vecchio del 2010... se non ricordo male, era un imo vecchiotto.
Re: Fattoriali $\rightarrow$ Naturali!
viewtopic.php?f=15&t=13435&p=110865
e a quanto pare era sul serio anche un vecchio test di ammissione al s. anna....
e a quanto pare era sul serio anche un vecchio test di ammissione al s. anna....
Re: Fattoriali $\rightarrow$ Naturali!
Supponi che $n$ abbia due rappresentazioni distinte $n=\displaystyle \sum_{1\le i\le k_1}{a_ii!}=\sum_{1\le i\le k_2}{b_ii!}$, con $k_1\ge k_2$; posto $b_{k_1+1}=b_{k_1+2}=\ldots=b_{k_2}=0$, sia $k_3$ il più grande intero tale che $a_i\neq b_i$. Allora:
$\displaystyle 0=n-n=\sum_{1\le i\le k_1}{(a_i-b_i)i!}$ $\displaystyle =\sum_{1\le i\le k_3}{(a_i-b_i)i!}\ge |a_{k_3}-b_{k_3}|k_3!-\left|\sum_{1\le i\le k_3-1}{(a_i-b_i)i!}\right|\ge $ $\displaystyle k_3!-\sum_{1\le i\le k_3-1}{i\cdot i!}=1$, che è assurdo. []
$\displaystyle 0=n-n=\sum_{1\le i\le k_1}{(a_i-b_i)i!}$ $\displaystyle =\sum_{1\le i\le k_3}{(a_i-b_i)i!}\ge |a_{k_3}-b_{k_3}|k_3!-\left|\sum_{1\le i\le k_3-1}{(a_i-b_i)i!}\right|\ge $ $\displaystyle k_3!-\sum_{1\le i\le k_3-1}{i\cdot i!}=1$, che è assurdo. []
The only goal of science is the honor of the human spirit.