1987 zeri per un fattoriale

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Cammy87
Messaggi: 144
Iscritto il: 10 mag 2005, 19:50
Località: Serra Riccò

1987 zeri per un fattoriale

Messaggio da Cammy87 » 09 apr 2007, 21:12

Dedicato ai nati nel 1987!! Dalla IMO Long list dell'87 appunto! :D

Trovare il più piccolo numero naturale $ n $ tale che $ n! $ abbia esattamente 1987 zeri.

Good work! :D
>>> Io sono la gomma e tu la colla! <<<
-----

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 09 apr 2007, 21:18

mi pare di averlo visto da poco su queste pagine, non ricordo se in TdN o in combinatoria...
:arrow:

Avatar utente
Cammy87
Messaggi: 144
Iscritto il: 10 mag 2005, 19:50
Località: Serra Riccò

Messaggio da Cammy87 » 09 apr 2007, 21:27

Uhmm non l'avevo visto! Semmai che è un doppione cancellate il mio messaggio. Io ho preso l'esercizio dal Pen, quindi è possibile che qualcun'altro lo avesse già postato. Comunque se per qualcuno è nuovo provi a farlo: è facile e carino! (almeno così mi è parso :roll: )
>>> Io sono la gomma e tu la colla! <<<
-----

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 09 apr 2007, 21:34

Cammy87 ha scritto:Uhmm non l'avevo visto! Semmai che è un doppione cancellate il mio messaggio. Io ho preso l'esercizio dal Pen, quindi è possibile che qualcun'altro lo avesse già postato. Comunque se per qualcuno è nuovo provi a farlo: è facile e carino! (almeno così mi è parso :roll: )
ah, allora può darsi che l'ho visto sul pen :wink:
comunque si, è bellino

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 10 apr 2007, 11:23

Anche se questo tipo di problema e conosciuto, rimane pur sempre un bel problema, ecco la mia soluzione:

Per trovare il numero di zeri di $ n! $,dobbiamo cercare il numero di volte che il numero e divisibile per $ 10 $, il che equivale a trovare il numero di volte che e presente il fattore 5 nella decompoosizione in fattori primi del numero, adesso, per vedere il numero di volte che $ 5^1 $ e presente nella decomposizione dobbiamo dividere n per $ 5^1 $ e prendere il massimo intero, per vedere il numero di volte che $ 5^2 $ e presente nella decomposizione dobbiamo dividere n per $ 5^2 $ e prendere il massimo intero, e cosi via.
Quindi il problema si riconduce a dire, per quale n si ha:

$ \sum_{k=1}^p[\frac{n}{5^k}] = 1987 $, con $ 5^{p-1}<n\leq 5^p $

Cosi a prima vista direi che $ n = 7960 $

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 10 apr 2007, 11:37

Credo che il problema intenda tutti gli 0 di $ n! $ non solo quelli a destra: per esempio 1020 è divisibile una volta per 10 ma ha due 0.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 10 apr 2007, 11:45

julio14 ha scritto:Credo che il problema intenda tutti gli 0 di $ n! $ non solo quelli a destra: per esempio 1020 è divisibile una volta per 10 ma ha due 0.
no, ha capito bene lui (forse ha scritto un pò male cammy), anche perchè non credo che avrebbe una soluzione altrimenti

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 10 apr 2007, 12:42

salva90 ha scritto:
julio14 ha scritto:Credo che il problema intenda tutti gli 0 di $ n! $ non solo quelli a destra: per esempio 1020 è divisibile una volta per 10 ma ha due 0.
no, ha capito bene lui (forse ha scritto un pò male cammy), anche perchè non credo che avrebbe una soluzione altrimenti
Colpa mia! Quando ho visto che riuscivo a farlo anch'io (in effetti così è parecchio facile) mi sono insospettito.
Contando tutti gli zeri una soluzione ce l'ha di sicuro (al limite 7960) ma credo che per un problema del genere più che un ragazzo di questo forum ci voglia un super calcolatore. Se qualcuno però ce la fa, meglio!
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 10 apr 2007, 13:01

Comunque 7960 e esatto, o c'e' un numero piu piccolo ( comunque nn credo che il problema sarebbe risolvibile, senza l'uso di un super calcolatore, se fossero 1987 zeri in totale, per questo ho pensato che potessero essere solo quelli a destra)?

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 10 apr 2007, 13:26

Jacobi ha scritto:Comunque 7960 e esatto, o c'e' un numero piu piccolo ( comunque nn credo che il problema sarebbe risolvibile, senza l'uso di un super calcolatore, se fossero 1987 zeri in totale, per questo ho pensato che potessero essere solo quelli a destra)?
se fosse un numero minore non potrebbe funzionare, già con 7959 hai (almeno) un 5 in meno

Avatar utente
Cammy87
Messaggi: 144
Iscritto il: 10 mag 2005, 19:50
Località: Serra Riccò

Messaggio da Cammy87 » 10 apr 2007, 13:47

Sì sì il risultato è 7960! Intendevo naturalmente gli zeri più a destra del fattoriale, forse mi sono espresso un po' male. Contando tutti gli zeri del numero il problema si complica notevolmente e non ho idea di come farlo se non con una marea di conti! :shock:

Il problema è abbastanza conosciuto e facile, ma i problemi con i fattoriali sono tra i miei preferiti! :D
>>> Io sono la gomma e tu la colla! <<<
-----

Zok
Messaggi: 140
Iscritto il: 01 gen 1970, 01:00
Località: Cambridge - Verona

Messaggio da Zok » 10 apr 2007, 13:51

Il risultato corretto è 7960, ma per chi non si accontenta del risultato numerico posto la mia soluzione completa...

n è sicuramente compreso tra 2 potenze di 5, cioè $ $ 5^k<n<5^{k+1} $
Il numero di fattori 5 nel fattoriale di $ $ 5^k $ è $ \displaystyle \sum_{i=1}^{k} \bigg [\frac{5^k}{5^i}\bigg ]=5^{k-1}+5^{k-2}+...+5+1=\frac{5^k-1}{4} $

Analogamente nel fattoriale di $ $ 5^{k+1} $ il numero dei fattori 5 è $ $ \frac{5^{k+1}-1}{4} $
Quindi se il fattore 5 deve comparire 1987 volte nel fattoriale di n vuol dire che:

$ $ \frac{5^k-1}{4}<1987<\frac{5^{k+1}-1}{4} $

Da cui $ $k=5 $ e quindi $ $5^5<n<5^6 $

Il numero di fattori 5 che compaiono nella fattorizzazione di n è quindi $ \displaystyle \sum_{i=1}^{5}\bigg [\frac{n}{5^i}\bigg]=\bigg[\frac{n}{5}\bigg]+\bigg[\frac{n}{25}\bigg]+\bigg[\frac{n}{125}\bigg]+\bigg[\frac{n}{625}\bigg]+\bigg[\frac{n}{3125}\bigg] $
Noi dobbiamo trovare n tale che $ $\bigg[\frac{n}{5}\bigg]+\bigg[\frac{n}{25}\bigg]+\bigg[\frac{n}{125}\bigg]+\bigg[\frac{n}{625}\bigg]+\bigg[\frac{n}{3125}\bigg]=1987 $
Siccome $ $ 1987=\sum_{i=1}^{5}\bigg [\frac{n}{5^i}\bigg]<\bigg[\frac{n}{5}+\frac{n}{25}+ \frac{n}{125}+\frac{n}{625}+\frac{n}{3125}\bigg] $

Zok
Messaggi: 140
Iscritto il: 01 gen 1970, 01:00
Località: Cambridge - Verona

Messaggio da Zok » 10 apr 2007, 13:52

Allora
$ $\bigg[\frac{n}{3125}\cdot (625+125+25+5+1) \bigg]>1987 $
$ $\bigg[\frac{n}{3125}\cdot 781 \bigg]>1987 $

Ma se la parte intera di un certo numero è maggiore di 1987 allora anche il numero stesso è maggiore di 1987.

Quindi $ $\frac{n}{3125}\cdot 781>1987 $ da cui $ n>7950 $
Tenendo conto che n (in quanto minimo) dev'essere un multiplo di 5, allora potrebbe essere 7955 (ma 7955! ha solo 1986 zeri infatti $ $ \sum_{i=1}^{5}\bigg [\frac{7955}{5^i}\bigg]=1896 $); il successivo multiplo di 5, 7960 invece va bene ed è il numero che si cercava.

[Ho dovuto spezzare il post perchè il LATEX mi stava impazzendo]

Avatar utente
Cammy87
Messaggi: 144
Iscritto il: 10 mag 2005, 19:50
Località: Serra Riccò

Messaggio da Cammy87 » 10 apr 2007, 14:47

Bella l'idea di sfruttare la disuguaglianza della parte intera Zok! :D
Io invece dopo aver visto tra quali potenze di 5 è compreso n, ho iniziato a valutare tra quali multipli delle potenze inferiori era compreso, cioè quanti fattori 5^4 dovessi avere, poi quanti 5^3 e così via fino a trovare esattamente il risultato.
Facendo come hai fatto te, però si riesce a dare subito una buona stima del numero! 8)
>>> Io sono la gomma e tu la colla! <<<
-----

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 10 apr 2007, 17:32

Cammy87 ha scritto:Il problema è abbastanza conosciuto e facile, ma i problemi con i fattoriali sono tra i miei preferiti! :D
Infatti i problemi con i fattoriali sono bellissimi :D

Rispondi