Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A C. 1581. feladat (2020. január)

C. 1581. Adjuk meg \(\displaystyle n\) azon pozitív egész értékeit, amelyekre \(\displaystyle n!\) pontosan \(\displaystyle 19\,531\) darab \(\displaystyle 0\)-ra végződik.

(5 pont)

A beküldési határidő 2020. február 10-én LEJÁRT.


Megoldás. Ahhoz, hogy lássuk, hogy \(\displaystyle n!\) hány 0-ra végződik azt kell megnéznünk, hogy a 2 és az 5 milyen hatványon szerepel a prímtényezős felbontásában (,,egy 2-5 pár ad ki egy 0-t''). Legyen a prímtényezős felbontás

\(\displaystyle n!=2^{\alpha(n)}\cdot 5^{\beta(n)}\dots... \)

Ekkor

\(\displaystyle \alpha(n)=\left\lfloor \frac{n}{2} \right\rfloor+ \left\lfloor \frac{n}{2^2} \right\rfloor+\left\lfloor \frac{n}{2^3} \right\rfloor+... ,\)

hiszen az \(\displaystyle n!=1\cdot 2\cdot \ldots \cdot n\) szorzatban \(\displaystyle \left\lfloor \frac{n}{2} \right\rfloor\) darab páros, \(\displaystyle \left\lfloor \frac{n}{2^2} \right\rfloor\) darab \(\displaystyle 2^2=4\)-gyel osztható, \(\displaystyle \left\lfloor \frac{n}{2^3} \right\rfloor\) darab \(\displaystyle 2^3=8\)-cal osztható tényező van, stb.

Ehhez hasonlóan

\(\displaystyle \beta(n)=\left\lfloor \frac{n}{5} \right\rfloor+ \left\lfloor \frac{n}{5^2} \right\rfloor+\left\lfloor \frac{n}{5^3} \right\rfloor+...\)

Mindkét összegben valahonnan kezdve az összes tag 0. Az utolsó nem 0 tag az \(\displaystyle n\)-nél nem nagyobb legnagyobb 2-hatványnál, illetve 5-hatványnál van. Látható, hogy \(\displaystyle \alpha \geq \beta,\) hiszen az \(\displaystyle \alpha\)-t adó összeg minden adott sorszámú tagja nagyobb, vagy egyenlő \(\displaystyle \beta\) megfelelő tagjánál.

Ezek alapján nézzük meg az 5-hatványok \(\displaystyle \beta\)-ját, hogy kiderítsük, \(\displaystyle n\) melyik kettő 5-hatvány közé esik:

\(\displaystyle \beta(5)=1,\)

\(\displaystyle \beta(5^2)=5+1=6,\)

\(\displaystyle \beta(5^3)=25+6=31,\)

\(\displaystyle \beta(5^4)=125+31=156,\)

\(\displaystyle \beta(5^5)=625+156=781,\)

\(\displaystyle \beta(5^6)=3125+781=3906,\)

\(\displaystyle \beta(5^7)=15625+3906=19531.\)

Azaz, ha \(\displaystyle n=5^7\), akkor \(\displaystyle n!=(5^7)!=78125!\) éppen 19531 darab 0-ra végződik. Természetesen az \(\displaystyle 5^7+1, 5^7+2, 5^7+3\) és \(\displaystyle 5^7+4\) számok \(\displaystyle \beta\)-ja is ennyi, azaz \(\displaystyle 5^7\leq n\leq 5^7+4\) esetén \(\displaystyle n!\) éppen 19531 darab 0-ra végződik. Ha \(\displaystyle n\) kisebb, mint \(\displaystyle 5^7\), akkor \(\displaystyle \beta\)-ja (legalább 7-tel) kisebb, mint 19531, tehát túl kevés 0-ra végződik. Ha \(\displaystyle n\) nagyobb vagy egyenlő, mint \(\displaystyle 5^7+5\), akkor pedig legalább 1-gyel több 0-ra végződik \(\displaystyle n!\).

Tehát \(\displaystyle n\) értéke a következők valamelyike lehet: \(\displaystyle 78125, 78126, 78127, 78128, 78129\).


Statisztika:

A C. 1581. feladat értékelése még nem fejeződött be.


A KöMaL 2020. januári matematika feladatai