Kezdőlap


Feladat:	B.4167	Korcsoport: 14-15	Nehézségi fok: nehéz
Megoldó(k):	Blázsik Zoltán , Bodor Bertalan , Dudás Zsolt , Éles András , Huszár Kristóf , Mester Márton , Nagy Donát , Tuan Nhat Le , Varga László
Füzet:	2010/január, 26 - 27. oldal		PDF \| MathML
Témakör(ök):	Feladat, Oszthatóság, Szorzat, hatvány számjegyei
Hivatkozás(ok):	Feladatok: 2009/március: B.4167

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. A keresett számokat nevezzük röviden jónak. Tegyük fel, hogy $k$ jó. Ekkor $k < 10^{m}$ teljesül alkalmas $m$ pozitív egész számmal, ezért $k$ -nak van olyan $n$ többszöröse, amelyre $10^{m} \leq n < 2 \cdot 10^{m}$ . Erre az $n$ számra $f (n)$ utolsó jegye 1-es, vagyis $f (n)$ nem osztható sem 2-vel, sem 5-tel. Ezért a $k$ szám relatív prím a 10-hez. Az Euler‐Fermat-tétel szerint így $9 k$ osztója $10^{t} - 1$ -nek, ahol $t = φ (9 k)$ . Ezért $k$ osztója a $t$ -jegyű, csupa 1-esből álló $K = \frac{10^{t} - 1}{9}$ számnak is. Tehát

\begin{matrix} k ∣ 19 K = 20 K - K = {\underset{︸}{22 ... 2}}_{t}^{} 0 - {\underset{︸}{11 ... 1}}_{t}^{} = 2 {\underset{︸}{11 ... 1}}_{t - 2}^{} 09, \end{matrix}

ahonnan

\begin{matrix} k ∣ f (19 K) = 90 {\underset{︸}{11 ... 1}}_{t - 2}^{} 2 \end{matrix}

adódik. Innen

\begin{matrix} k ∣ L = f (19 K) - 80 K = 90 {\underset{︸}{11 ... 1}}_{t - 2}^{} 2 - {\underset{︸}{88 ... 8}}_{t}^{} 0 = 1 {\underset{︸}{22 ... 2}}_{t - 3}^{} 32, \end{matrix}

majd

\begin{matrix} k ∣ 2 K - L = {\underset{︸}{22 ... 2}}_{t}^{} - 1 {\underset{︸}{22 ... 2}}_{t - 3}^{} 32 = 10^{t - 1} - 10 \end{matrix}

következik. Mindent összevetve kapjuk, hogy

\begin{matrix} k ∣ (10^{t} - 1) - 10 (10^{t - 1} - 10) = 99, \end{matrix}

vagyis

k

lehetséges értékei 1, 3, 9, 11, 33 és 99. A 3-as, 9-es és 11-es oszthatósági szabályok ismeretében könnyen meggyőződhetünk arról, hogy ezen hat szám mindegyike valóban jó.

Megjegyzés. A megoldásban az Euler‐Fermat-tételre csak annyiban volt szükség, hogy belássuk, a

k

-nak létezik csupa 1-es számjegyből álló többszöröse. Ezt viszont már a skatulya-elv alkalmazásával is megkaphatjuk. Tekintsük ehhez az

1,11,111,1111, ...

számokat. Ha a sorozatot elég hosszan folytatjuk, biztosan lesz két olyan szám, amely ugyanazt a maradékot adja

k

-val osztva; ha ez az

a

és a

b

darab 1-esből álló szám, (ahol

a < b

) akkor különbségük

\begin{matrix} {\underset{︸}{11 ... 1}}_{b - a}^{} {\underset{︸}{00 ... 0}}_{a}^{} = 10^{a} \cdot {\underset{︸}{11 ... 1}}_{b - a}^{} \end{matrix}

osztható

k

-val. Mivel

k

relatív prím a 10-hez, azért

{\underset{︸}{11 ... 1}}_{b - a}^{}

is osztható

k

-val.