Brojevi zadanih oblika (zadatak)

[morena_007]

Molim sve ljude dobre volje i matematičke znalce da mi pomognu s ova 3 zadatka:

1) Dokažite da za svaki prirodni broj n postoji višekratnik od n dekadskog oblika 11111…1000…0

2) Dokažite da postoji potencija broja 3 koja u dekadskom zapisu završava
znamenkama 0001

3) Dokažite da postoji potencija broja 2 koja u dekadskom zapisu počinje sa 99999

[kikzmyster]

1) je rijesen ovdje:
Samo zamijeni "2013" sa "n".

2) Pretpostavljam da se trazi prirodna potencija (inace trivijalno imamo [tex]3^0 = 1[/tex]). Iskoristimo Eulerov teorem: Za prirodne brojeve [tex]a[/tex] i [tex]b[/tex] koji su relativno prosti vrijedi [tex] a ^ {\varphi(b)} \equiv 1 (\textrm{mod } b) [/tex], pri cemu je [tex]\varphi(b) [/tex] broj prirodnih brojeva koji su relativno prosti s [tex]b[/tex]. Uocimo da su [tex]3[/tex] i [tex]10000[/tex] relativno prosti, pa primijenimo teorem za [tex]a=3[/tex] i [tex]b=10000[/tex]. Trazena potencija je [tex]3^{\varphi(10000)}[/tex].

3) Pitamo se postoje li prirodni brojevi [tex]m,n[/tex] takvi da vrijedi [tex]99999 \cdot 10^n \leq 2^m < 100000 \cdot 10^n [/tex]. Logaritmiranjem (po bazi 10, da tvrdnja o iracionalnosti koja slijedi bude elementarna) dobivamo ekvivalentnu nejednakost: [tex] \log(99999) +n \leq m \log 2 < \log(100000) +n [/tex], tj. [tex] \log(99999) \leq m \log 2 - n < \log(100000) [/tex]. Sada cemo iskoristiti da je [tex]\log 2 [/tex] iracionalan broj. Naime, moze se pokazati da su za proizvoljni iracionalan broj [tex]r[/tex] brojevi oblika [tex]mr - n[/tex] gusti u [tex]\mathbb{R}[/tex] (dokaz ovog mozes naci ovdje, pod "Uses and applications", drugi paragraf, samo reci ako treba jos pojasniti), pa posebno postoje [tex]m, n[/tex] takvi da je zadovoljena gornja nejednakost.

[morena_007]

[kikzmyster]

Pokazat cemo prvo da za proizvoljni [tex] \epsilon > 0[/tex] i iracionalan broj [tex]r>0[/tex] postoje prirodni brojevi [tex]n,m[/tex] takvi da je [tex] 0 < n - mr < \epsilon[/tex]. Neka je [tex]M[/tex] dovoljno velik prirodan broj takav da je [tex]\frac{1}{M} < \epsilon[/tex]. Promatramo sljedecu particiju skupa [tex] [ 0 , +\infty \rangle [/tex]: [tex]A_1 = \{ \langle i , i+ \frac{1}{M} ] \mid i \in \mathbb{N}\cup \{0\} \}, \ A_2 = \{ \langle i + \frac{1}{M} , i+ \frac{2}{M} ] \mid i \in \mathbb{N}\cup \{0\} \}, \ \ldots \ , \ A_j = \{ \langle i + \frac{j-1}{M} , i+ \frac{j}{M} ] \mid i \in \mathbb{N}\cup \{0\} \}, \ldots, \ A_M = \{ \langle i + \frac{M-1}{M} , k+ 1 ] \mid i \in \mathbb{N}\cup \{0\} \}.[/tex]

Sad po "pigeonhole principle" (Dirichletovom principu) postoje [tex]m_1, m_2 \in \{1,2,\ldots, M+1\}[/tex], [tex]m_1 \neq m_2[/tex], takvi da su [tex]m_1 r[/tex] i [tex]m_2 r[/tex] u istom [tex]A_k[/tex] (jer postoji [tex]M[/tex] skupova [tex]A_i[/tex], a [tex]M+1[/tex] brojeva oblika [tex]l r [/tex], za [tex]l \in \{1,2,\ldots, M+1\} [/tex], pa postoji neki [tex]k[/tex] t.d. je [tex]A_k[/tex] pogoden barem dvaput).

Dakle, imamo [tex]m_1 r \in \langle p + \frac{k}{M}, p + \frac{k+1}{M} ] [/tex] i [tex]m_2 r \in \langle q + \frac{k}{M}, q + \frac{k+1}{M} ] [/tex], za neke prirodne brojeve [tex]p,q[/tex]. No, uocimo da mozemo iskljuciti desne rubove ovih intervala: zaista, [tex]m_1 r = p + \frac{k+1}{M}[/tex] bi povlacilo da je [tex] r = \frac{p}{m_1} + \frac{k+1}{M n_1} \in \mathbb{Q}[/tex], sto je kontradikcija. Slicno za [tex]m_2 r [/tex]. Sad kad znamo da je [tex]m_1 r \in \langle p + \frac{k}{M}, p + \frac{k+1}{M} \rangle [/tex] i [tex]m_2 r \in \langle q + \frac{k}{M}, q + \frac{k+1}{M} \rangle [/tex], dobivamo da se [tex](m_2 - m_1)r[/tex] mora nalaziti u intervalu [tex]( q - p - \frac{1}{M}, q - p + \frac{1}{M} \rangle[/tex].

Uzmimo sada bez smanjenja opcenitosti da je [tex](m_2 - m_1) r \in ( q - p - \frac{1}{M}, 0 \rangle [/tex] (inace, ako je [tex](m_2 - m_1) r \in \langle 0, q - p + \frac{1}{M} \rangle [/tex], umjesto [tex](m_2 - m_1)r[/tex] uzmemo [tex](m_1-m_2)r[/tex] pa imamo [tex](m_1 - m_2) r \in \langle p - q - \frac{1}{M}, 0 \rangle [/tex]). Uocimo da je sada [tex](q-p) - (m_2 - m_1)r \in \langle 0 , \frac{1}{M} \rangle[/tex]. Dakle, uzmemo li [tex]n= q-p, \ m = m_2 - m_1 [/tex], nasli smo [tex]m[/tex] i [tex] n [/tex] takve da je [tex] 0 < n - mr < \frac{1}{M} < \epsilon[/tex]. Obrazlozimo jos zasto ne moze biti [tex]n-mr = 0[/tex] : To bi povlacilo [tex] r = \frac{n}{m} \in \mathbb{Q}[/tex], sto je kontradikcija.

Sad kad znamo da vrijedi ovo gore, pokazimo da za proizvoljne [tex]x, y > 0[/tex] postoje [tex]m, n [/tex] takvi da je [tex]n-mr \in \langle x, y \rangle[/tex] (u zadatku nam ovo treba za [tex]x= \log (99999), y = \log(100000)[/tex]. Uzmimo bez smanjenja opcenitosti da je [tex]x < y[/tex]. Po gore dokazanom, postoje [tex]m_1, n_1 [/tex] takvi da je [tex] 0< n_1 - m_1r < \frac{y-x}{2}[/tex]. Sad po Arhimedovom aksiomu postoji prirodni broj [tex]n_0[/tex] takav da je [tex] n_0(n_1 - m_1 r) = n_0n_1 - n_0m_1r \in \langle x, y \rangle [/tex] (zaista, zamisli sve brojeve oblika [tex]k \cdot (n_1 - m_1 r)[/tex]. Kako je [tex] n_1 - m_1 r [/tex] manji od pola udaljenosti od [tex]x[/tex] do [tex]y[/tex], jedan od tih brojeva mora upasti tocno izmedu [tex]x[/tex] i [tex]y[/tex].) Uzmemo li [tex]n = n_0 n_1, m = n_0 m_1[/tex], nasli smo trazene [tex]m,n[/tex].

[morena_007]