Matematyka.pl

Dzisiaj w całej Polsce odbył się 2. etap Olimpiady. Oto pierwsze zadanie:

Wyznacz największą liczbę naturalną \(\displaystyle{ k}\) taką, że liczba \(\displaystyle{ 2016!}\) jest wielokrotnością liczby \(\displaystyle{ 10^{k}}\).

Niestety, ale nie potrafiłam i nadal nie potrafię rozwiązać tego zadania. Może ktoś coś podpowie?

Należy znaleźć wszystkie liczby mniejsze lub równe 2016, które są wielokrotnością 5 lub 2, a następnie policzyć, ile razy łącznie występuje liczba 2 i 5. Można to zrobić, wyznaczając liczbę wielokrotności 2, 4, 8, itd. oraz 5, 125, 625, itd., zwracając uwagę na to, ile razy dana liczba zostanie "policzona". Mam nadzieję, że zbytnio nie namieszałem.

\(\displaystyle{ n!}\) to iloczyn wszystkich liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\) włącznie, w tym przypadku mamy \(\displaystyle{ 2016! = 1 \cdot 2 \cdot 3 \cdot ... \cdot 2016}\). W zadaniu należy znaleźć największą potęgę liczby \(\displaystyle{ 10}\) dzielącą \(\displaystyle{ 2016!}\). Konkretniej wykładnik tej potęgi, czyli liczbę \(\displaystyle{ k}\). Zauważmy, że \(\displaystyle{ 10 = 2 \cdot 5}\) (rozkład liczby \(\displaystyle{ 10}\) na czynniki pierwsze). Rozłóżmy teraz \(\displaystyle{ 2016!}\) na czynniki pierwsze, nie dosłownie, lecz teoretycznie. Będzie to \(\displaystyle{ 2^{\alpha_{2}}}\) razy \(\displaystyle{ 3^{\alpha_{3}}}\) razy \(\displaystyle{ 5^{\alpha_{5}}}\) i tak dalej dla pewnych wykładników \(\displaystyle{ \alpha_{i}}\). Zatem, żeby rozwiązać zadanie, należy znaleźć \(\displaystyle{ \alpha_{2}}\) oraz \(\displaystyle{ \alpha_{5}}\), czyli ile dwójek i piątek wystąpi w rozkładzie \(\displaystyle{ 2016!}\) na czynniki pierwsze. Wtedy będziemy wiedzieć ile dziesiątek, czyli liczb postaci \(\displaystyle{ 2 \cdot 5}\) można utworzyć. Możemy już zdefiniować \(\displaystyle{ k = \min(\alpha_{2}, \alpha_{5})}\). Nietrudno jednak zauważyć, że \(\displaystyle{ \alpha_{2} < \alpha_{5}}\), ponieważ w przedziale od \(\displaystyle{ 1}\) do \(\displaystyle{ 2{}016}\) znajduje się znacznie więcej liczb podzielnych przez \(\displaystyle{ 2}\) (jest to co druga liczba) niż przez \(\displaystyle{ 5}\) (co piąta liczba), zatem możemy się ograniczyć tylko do policzenia \(\displaystyle{ \alpha_{5}}\).

Przejdźmy teraz do policzenia \(\displaystyle{ \alpha_{5}}\). Zdefiniujmy najpierw \(\displaystyle{ \left[ x \right]}\) jako część całkowitą liczby \(\displaystyle{ x}\). Dla przykładu \(\displaystyle{ \left[ 46,9 \right] = 46}\), \(\displaystyle{ \left[ 51,2 \right] = 51}\). Liczb podzielnych przez \(\displaystyle{ 5}\) jest \(\displaystyle{ \left[ \frac{2016}{5} \right]}\) (co piąta liczba). Czy to wszystkie piątki z rozkładu \(\displaystyle{ 2016!}\)? Otóż nie, ponieważ są jeszcze wielokrotności liczby \(\displaystyle{ 25 = 5 * 5}\), czyli \(\displaystyle{ 25, 50, 75, 100, ...}\). Każdą taką liczbę policzyliśmy jeden raz, jako wielokrotność \(\displaystyle{ 5}\), ale przecież w nich piątka występuje dwa razy. Zatem musimy dodać \(\displaystyle{ \left[ \frac{2016}{25} \right]}\). Bardzo podobnie jest z wielokrotnościami \(\displaystyle{ 125 = 5 \cdot 5 \cdot 5}\), czyli \(\displaystyle{ 125, 250, 375, ...}\). Ich ilość to ponownie \(\displaystyle{ \left[ \frac{2016}{125} \right]}\). Dalej mamy \(\displaystyle{ 625 = 5 \cdot 5 \cdot 5 \cdot 5}\), więc dodajemy \(\displaystyle{ \left[ \frac{2016}{625} \right]}\). Następną potęgą piątki jest \(\displaystyle{ 3125}\), ale \(\displaystyle{ 3125 > 2016}\), więc \(\displaystyle{ \left[ \frac{2016}{3125} \right] = 0}\). To samo dla kolejnych potęg piątki, więc tu zatrzymujemy sumowanie.

Podsumowując \(\displaystyle{ k = \alpha_{5} = \left[ \frac{2016}{5} \right] + \left[ \frac{2016}{25} \right] + \left[ \frac{2016}{125} \right] + \left[ \frac{2016}{625} \right] = 403 + 80 + 16 + 3 = 502}\).

Jako pewne uogólnienie, bądź wniosek z tego zadania podam następujący fakt:
Wykładnik liczby pierwszej \(\displaystyle{ p}\) w rozkładzie \(\displaystyle{ n!}\) na czynniki pierwsze to \(\displaystyle{ \sum_{i = 1}^{\infty}\left[ \frac{n}{p^{i}} \right]}\)

Valiors- dziękuję bardzo za pomoc! Wszystko tak klarownie wyjaśnione

Valiors pisze:Nietrudno jednak zauważyć, że \(\displaystyle{ \alpha_{2} < \alpha_{5}}\), ponieważ w przedziale od \(\displaystyle{ 1}\) do \(\displaystyle{ 2{}016}\) znajduje się znacznie więcej liczb podzielnych przez \(\displaystyle{ 2}\) (jest to co druga liczba) niż przez \(\displaystyle{ 5}\) (co piąta liczba),[/latex].

Raczej \(\displaystyle{ \alpha_{2} > \alpha_{5}}\).

JK