Niech \(\displaystyle{ n}\) oznacza łączną liczbę włosów na głowach wszystkich ludzi żyjących obecnie na Ziemi. Rozstrzygnij, co jest większe: długość zapisu dziesiętnego liczby \(\displaystyle{ 2^n}\) czy liczba końcowych zer w zapisie dziesiętnym liczby \(\displaystyle{ n!}\).
Zależy mi na pokazaniu tego, bo nie bardzo potrafię do tego podejść. Chodzi o podejście asymptotyczne.
Rostrzygnąć o rozmiarze liczb.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Rostrzygnąć o rozmiarze liczb.
Na końcu \(\displaystyle{ n!}\) jest tyle zer ile jest piątek w rozkładzie na czynniki pierwsze liczby \(\displaystyle{ n!}\).
Tych zaś jest \(\displaystyle{ P= \sum_{k\ge 1}^{}[\frac{n}{5^k}]< \sum_{k\ge 1}^{}\frac{n}{5^k} \leq n/4}\)
\(\displaystyle{ n/4<n \log_{10}{2}}\)
Tych zaś jest \(\displaystyle{ P= \sum_{k\ge 1}^{}[\frac{n}{5^k}]< \sum_{k\ge 1}^{}\frac{n}{5^k} \leq n/4}\)
\(\displaystyle{ n/4<n \log_{10}{2}}\)
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
Rostrzygnąć o rozmiarze liczb.
Jak rozumiem, efekt taki, że \(\displaystyle{ 2^n}\) wygrywa.
Zadam kilka pytań kontrolnych.
Skąd pewność, że właśnie tak jest z tymi czynnikami - ilość zer równa ilości piątek ?
Ja rozumiem, że \(\displaystyle{ 10 = 5 * 2}\), ale no właśnie, dwójka. Tzn ja uważam, że trzeba parować dwójki i piątki, ale ale:
Można patrzeć na piątki, bo gdy się pojawiła piąta, to wcześniej musiała się pojawić dwójka w rozkładzie, tzn np:
\(\displaystyle{ 15!}\)
mamy \(\displaystyle{ 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 *15}\)
Ile zer może mieć ta liczba ? Tyle ile 10tek w rozkładzie, a więc tyle ile piątek, bo:
pierwsza piątka się pojawia, ale wcześniej już pojawiła się dwójka. Tak samo w przypadku \(\displaystyle{ 15}\) - zdążyliśmy mieć mnóstwo liczb parzystych po drodze, a więc i dwójek.
Czyli, tak na prawdę wynika to, że liczb parzystych jest znacznie gęściej (choć tyle samo) co liczb podzielnych przez \(\displaystyle{ 5}\).
Szacowania już rozumiem, tylko tego jednego nie jestem pewien.
Zadam kilka pytań kontrolnych.
Skąd pewność, że właśnie tak jest z tymi czynnikami - ilość zer równa ilości piątek ?
Ja rozumiem, że \(\displaystyle{ 10 = 5 * 2}\), ale no właśnie, dwójka. Tzn ja uważam, że trzeba parować dwójki i piątki, ale ale:
Można patrzeć na piątki, bo gdy się pojawiła piąta, to wcześniej musiała się pojawić dwójka w rozkładzie, tzn np:
\(\displaystyle{ 15!}\)
mamy \(\displaystyle{ 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 *15}\)
Ile zer może mieć ta liczba ? Tyle ile 10tek w rozkładzie, a więc tyle ile piątek, bo:
pierwsza piątka się pojawia, ale wcześniej już pojawiła się dwójka. Tak samo w przypadku \(\displaystyle{ 15}\) - zdążyliśmy mieć mnóstwo liczb parzystych po drodze, a więc i dwójek.
Czyli, tak na prawdę wynika to, że liczb parzystych jest znacznie gęściej (choć tyle samo) co liczb podzielnych przez \(\displaystyle{ 5}\).
Szacowania już rozumiem, tylko tego jednego nie jestem pewien.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Rostrzygnąć o rozmiarze liczb.
Dwójek jest nie mniej niż piątek w rozkładzie na czynniki pierwsze liczby \(\displaystyle{ n!}\). To jest fakt, który podałem bez dowodu. Bez dowodu podałem też wzór na krotność piątki w rozkładzie \(\displaystyle{ n!}\), z którego wynika powyższy fakt.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
Rostrzygnąć o rozmiarze liczb.
To właśnie miałem na myśli. Co prawda bez dowodu, ale sądzę, że łatwo w to uwierzyć.Dwójek jest nie mniej niż piątek w rozkładzie na czynniki pierwsze liczby \(\displaystyle{ n!.}\)
To też można wydedukować bez dowodu, tzn nie jest to coś skomplikowanego.Bez dowodu podałem też wzór na krotność piątki w rozkładzie \(\displaystyle{ n!}\), z którego wynika powyższy fakt.
Pozdrawiam!