Kezdőlap


Feladat:	N.21	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Burcsi Péter , Csörnyei Marianna , Futó Gábor , Gyarmati Katalin , Hertz István , Szeidl Ádám
Füzet:	1994/október, 364. oldal		PDF \| MathML
Témakör(ök):	Maradékos osztás, Skatulyaelv, Számjegyekkel kapcsolatos feladatok, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1994/február: N.21

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.

Feltehetjük, hogy $10^{4} \leq k$ , mert ha $k$ legfeljebb négyjegyű, akkor a feladat állítása nyilvánvaló. Tekintsük azokat a $(0 =) a_{0} < a_{1} < a_{2} < ...$ természetes számokat, amelyek tízes számrendszerbeli alakjában csak a 0 és az 1 számjegyek szerepelnek. Ha a tízes számrendszerbeli alakokat a kettes számrendszerben képzeljük el, akkor világos, hogy így minden természetes számot felsorolhatunk, és mindegyiket csak egyszer (tehát $a_{i}$ -ből éppen $i$ lesz). Ezért

\begin{matrix} a_{2^{n}} = a_{100 ... 0_{2}} = 1 {\overset{}{\overset{︷}{00 ... 0}}}_{}^{n db} = 10^{n} . \end{matrix}

A skatulyaelv szerint az

a_{0} < a_{1} < a_{2} < ... < a_{k}

számok között van kettő, amelyek

k

-val osztva ugyanazt a maradékot adják, azaz e két szám (pozitív) különbsége osztható

k

-val. Az írásbeli kivonás szabályait használva megállapíthatjuk, hogy e különbség tízes számrendszerbeli alakja csak a 0, 1, 8 és 9 számjegyeket tartalmazhatja, az pedig nyilvánvaló, hogy a különbség nem haladhatja meg

a_{k}

-t. Így elegendő belátnunk, hogy

a_{k} \leq k^{4}

. A fenti összefüggés ‐ és a megoldás elején tett feltevés ‐ segítségével ez is egyszerű:

\begin{matrix} \begin{matrix} a_{k} & \leq a_{2^{⌈ log_{2} k ⌉}} = 10^{⌈ log_{2} k ⌉} < 10^{1 + log_{2} k} = 10^{(log_{2} 10) (log_{2} k)} = 10 \cdot k^{log_{2} 10} = \\ = {(10^{2} \cdot k^{2 log_{2} 10})}^{1 / 2} < {(k \cdot k^{2 log_{2} 10})}^{1 / 2} = {(k^{log_{2} 200})}^{1 / 2} < {(k^{log_{2} 256})}^{1 / 2} = k^{4} . \end{matrix} \end{matrix}

Hertz István (Fazekas M. Főv. Gyak. Gimn., IV. o. t.) dolgozata alapján