OliForum Matematico

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

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

Good work!

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

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 )

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 )

ah, allora può darsi che l'ho visto sul pen
comunque si, è bellino

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 $

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.

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

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!

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)?

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

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!

Il problema è abbastanza conosciuto e facile, ma i problemi con i fattoriali sono tra i miei preferiti!

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] $

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]

Bella l'idea di sfruttare la disuguaglianza della parte intera Zok!
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!

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

Infatti i problemi con i fattoriali sono bellissimi