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

Posty: 77
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: 4
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: 163
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: 77
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: 21656
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 
 "Wygraj Indeks" - Politechnika Gdańska  MrLan  0
 GMiL edycja 2014  pitgot  17
 [OI] Przygotowanie do Olimpiady  Mati2000xcx  5
 V Edycja Ogólnopolskiej Olimpiady "O Diamentowy Indeks AGH"  Mruczek  146
 Dowodzenie i równanie - Diamentowy Indeks AGH  419862391432  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl