szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 31 sty 2016, o 19:34 
Użytkownik

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

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

Niestety, ale nie potrafiłam i nadal nie potrafię rozwiązać tego zadania. Może ktoś coś podpowie?
Góra
Mężczyzna Offline
PostNapisane: 31 sty 2016, o 22:20 
Użytkownik

Posty: 6
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.
Góra
Mężczyzna Offline
PostNapisane: 1 lut 2016, o 13:42 
Użytkownik

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

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

Podsumowując 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 p w rozkładzie n! na czynniki pierwsze to \sum_{i = 1}^{\infty}\left[ \frac{n}{p^{i}} \right]
Góra
Kobieta Offline
PostNapisane: 6 mar 2016, o 13:37 
Użytkownik

Posty: 81
Valiors- dziękuję bardzo za pomoc! Wszystko tak klarownie wyjaśnione :)
Góra
Mężczyzna Offline
PostNapisane: 6 mar 2016, o 13:40 
Administrator

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

Raczej \alpha_{2} > \alpha_{5}.

JK
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 III Edycja Ogólnopolskiej Olimpiady "O Diamentowy Indeks AGH  Tomek_Z  292
 GMIL - edycja 2015  Sylwek  4
 [OI] Przygotowanie do Olimpiady Informatycznej  Raveen  5
 Olimpiada "O diamentowy indeks AGH"  Benny01  97
 Awesome news z finału XIX Olimpiady Informatycznej  humanistyczna dusza  9
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl