Fattoriali $\rightarrow$ Naturali!

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
LukasEta
Messaggi: 245
Iscritto il: 04 dic 2008, 15:47

Fattoriali $\rightarrow$ Naturali!

Messaggio da LukasEta »

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$
Ἀγεωμέτρητος μηδεὶς εἰσίτω
staffo
Messaggi: 305
Iscritto il: 01 mar 2010, 15:34

Re: Fattoriali $\rightarrow$ Naturali!

Messaggio da staffo »

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?
[tex]\Lambda \eta \delta r \epsilon \alpha[/tex]
Sonner
Messaggi: 364
Iscritto il: 12 feb 2009, 16:02
Località: Susa (TO)

Re: Fattoriali $\rightarrow$ Naturali!

Messaggio da Sonner »

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)! $
Avatar utente
LukasEta
Messaggi: 245
Iscritto il: 04 dic 2008, 15:47

Re: Fattoriali $\rightarrow$ Naturali!

Messaggio da LukasEta »

Era da un test di ammissione al Sant'Anna per Ingegneria!
Ἀγεωμέτρητος μηδεὶς εἰσίτω
max tre
Messaggi: 159
Iscritto il: 15 giu 2010, 23:11

Re: Fattoriali $\rightarrow$ Naturali!

Messaggio da max tre »

LukasEta ha scritto:Era da un test di ammissione al Sant'Anna per Ingegneria!
sicuro?
galileiana 2010 matematica.pdf
esercizio 7, punti ii) e iii)
(79.73 KiB) Scaricato 242 volte
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: Fattoriali $\rightarrow$ Naturali!

Messaggio da ma_go »

era ben più vecchio del 2010... se non ricordo male, era un imo vecchiotto.
max tre
Messaggi: 159
Iscritto il: 15 giu 2010, 23:11

Re: Fattoriali $\rightarrow$ Naturali!

Messaggio da max tre »

viewtopic.php?f=15&t=13435&p=110865
e a quanto pare era sul serio anche un vecchio test di ammissione al s. anna....
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Fattoriali $\rightarrow$ Naturali!

Messaggio da jordan »

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. []
The only goal of science is the honor of the human spirit.
Rispondi