Feladat:	N.74	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor ,  Burcsi Péter ,  Elek Péter ,  Frenkel Péter ,  Gyarmati Katalin ,  Kutalik Zoltán ,  Terék Zsolt ,  Terpai Tamás ,  Tóth Gábor Zsolt ,  Vörös Zoltán ,  Zubcsek Péter Pál
Füzet:	1996/május, 291 - 293. oldal		PDF  |  MathML
Témakör(ök):	Euler-Fermat-tételek, Skatulyaelv, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1995/szeptember: N.74

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.   I. megoldás. a) Nyilván elegendő belátnunk, hogy minden $n$ pozitív egésznek van olyan többszöröse, amely csak a 0 és 1 számjegyeket tartalmazza. Tekintsük ehhez az $\begin{array}{c}{\displaystyle \mathrm{1,11,111,}\text{...}\mathrm{,}\underset{n+1\text{db}}{\overset{}{\underbrace{11\text{...}1}}}}\end{array}$ ,,csupaegy'' számokat. Ezek közül valamelyik kettő ugyanazt a maradékot adja $n$-nel osztva a skatulya-elv alapján, különbségük tehát $n$-nek többszöröse, amely természetesen csak a 0 és 1 számjegyeket tartalmazza. b) Teljes indukcióval igazoljuk, hogy minden $n$ pozitív egészhez található $n$-tarka szám, vagyis a feladatnak erre a részére igenlő a válasz. 1-tarka szám nyilvánvalóan létezik, ilyen pl. az $1234567890$. Tegyük fel, hogy $n$-tarka számot már találtunk, jelöljük $A$-val: ennek segítségével konstruálni fogunk egy $\left(n+1\right)$-tarka számot, ami igazolja állításunkat. A kérdéses $\left(n+1\right)$-tarka számot keressük a $C={10}^{l}A+B$ alakban, ahol $l$ és $B$ pozitív egészek. Ha $1\le m\le n+1$, akkor $\begin{array}{c}{\displaystyle mC={10}^l\left(mA\right)+mB}\end{array}$ tartalmazza mindazokat a számjegyeket, amiket $mA$ és $mB$, feltéve, hogy $mB<{10}^l$. Legyen ezért $l$ a $B$-től függően olyan, hogy teljesítse az $\begin{array}{c}{\displaystyle \left(n+1\right)B<{10}^l}\end{array}$ egyenlőtlenséget, ekkor $C$ mindenesetre $n$-tarka az indukciós feltevés és az előbbi észrevétel alapján, sőt $\left(n+1\right)$-tarka is, ha biztosítani tudjuk, hogy $\left(n+1\right)B$ mind a 10 számjegyet tartalmazza, más szóval 1-tarka legyen. Most már tehát csak egy megfelelő $B$-t kell találnunk. Ha pl. $k$ olyan egész, hogy $n<{10}^k$, akkor az $\begin{array}{c}{\displaystyle 1234567890\cdot {10}^k+j\left(0\le j\le n\right)}\end{array}$ alakú egész számok 1-tarkák, és minden lehetséges maradékot kiadnak $\left(n+1\right)$-gyel osztva. Van tehát közöttük $\left(n+1\right)$-nek egy $B$ többszöröse is, amely 1-tarka. Ezzel $B$-t, tehát $C$-t is előállítottuk, ami biztosítja az indukciós lépést és állításunk helytálló voltát.  Braun Gábor (Budapest, Szent István Gimn., III. o. t.)   II. megoldás. a) Tegyük fel, hogy az $n$ szám tarka. Legyen az $n$ prímtényezős felbontásában a 2, ill. az 5 kitevője $\alpha$, ill. $\beta$, azaz $\begin{array}{c}{\displaystyle n=2^{\alpha }{5}^{\beta }{n}_1\mathrm{,}\text{ahol}\left(n_1\mathrm{,10}\right)=1.}\end{array}$ Ekkor $\begin{array}{c}{\displaystyle n_2={10}^{\underset{}{\overset{}{\text{max}}}\left(\alpha \mathrm{,}\beta \right)}{n}_1}\end{array}$ is tarka, hiszen többszöröse $n$-nek. Az Euler‐Fermat tétel szerint $\begin{array}{c}{\displaystyle n_1\mid {10}^{\phi \left(n_1\right)}-\mathrm{1,}}\end{array}$ azaz $\begin{array}{c}{\displaystyle n_2\mid {10}^{\underset{}{\overset{}{\text{max}}}\left(\alpha \mathrm{,}\beta \right)}\left({10}^{\phi \left(n_1\right)}-1\right)\mathrm{.}}\end{array}$ Ez azonban azt jelenti, hogy $n_2$-nek van olyan többszöröse, amely $\phi \left(n_1\right)$ db 9-esből és $\underset{}{\overset{}{\text{max}}}\left(\alpha \mathrm{,}\beta \right)$ db 0-ból áll, tehát $n_2$ mégsem tarka. Az ellentmondás igazolja az a) állítást. b) Megmutatjuk, hogy minden $n$ pozitív egészhez található $n$-tarka szám, sőt bizonyos értelemben majdnem minden pozitív egész $n$-tarka. A bizonyításhoz bevezetjük a pozitív egészekből álló halmazok sűrűségének fogalmát. Ha $A$ egy pozitív egészekből álló halmaz, akkor jelölje $A\left(x\right)$ az $A$ halmaz $x$-nél nem nagyobb elemeinek a számát, továbbá értelmezzük az $A$ sűrűségét mint $\begin{array}{c}{\displaystyle \underset{x\to \infty }{\overset{}{\text{lim}}}\frac{A\left(x\right)}{x}\mathrm{,}}\end{array}$ ha ez a határérték létezik. Azt fogjuk bizonyítani, hogy az $n$-tarka számok sűrűsége 1, amiből rögtön következik az is, hogy van $n$-tarka szám. Mindenekelőtt az 1-tarka számokról mutatjuk ki, hogy 1 sűrűségűek, más szóval 0 a sűrűsége azoknak a pozitív egészeknek, amelyek nem tartalmazzák mind a 10 számjegyet. Jelölje $R$ ez utóbbi számok halmazát. Mivel egy $x$ korlátot meg nem haladó pozitív egészek legfeljebb $1+\left[\text{lg}x\right]$ jegyűek, ezért egy adott számjegyet nem tartalmazó pozitív egészek száma $x$-ig legfeljebb $\begin{array}{c}{\displaystyle 9+9^2+9^3+\cdot +9^{1+\left[\text{lg}x\right]}=9\frac{9^{1+\left[\text{lg}x\right]}-1}{8}<9^{2+\text{lg}x}\mathrm{.}}\end{array}$ Ebből rögtön adódik, hogy $\begin{array}{c}{\displaystyle \frac{R\left(x\right)}{x}<\frac{10\cdot 9^{2+\text{lg}x}}{x}=10\cdot 9^2{\left(\frac{9}{10}\right)}^{\text{lg}x}\mathrm{,}}\end{array}$ vagyis $x\to \infty$ esetén $\begin{array}{c}{\displaystyle \frac{R\left(x\right)}{x}\to \mathrm{0,}}\end{array}$ és ezt akartuk bizonyítani. Ezek után az $n$-tarka számokról mutatjuk meg, hogy 1 sűrűségűek, vagyis 0 a sűrűsége azoknak a pozitív egészeknek, amelyeknek valamilyen $1\le m\le n$ egésszel vett szorzata $R$-be esik. Ha $R_n$ jelöli ezen utóbbi számok halmazát, akkor tehát $\begin{array}{c}{\displaystyle R_n\left(x\right)\le \sum _{m=1}^n\sum _{\begin{array}{c}\hfill k\le x\hfill \\ \hfill mk\in R\hfill \end{array}}^{}1\le \sum _{m=1}^{n}R\left(mx\right)\mathrm{,}}\end{array}$ amiből $\begin{array}{c}{\displaystyle \frac{R_n\left(x\right)}{x}\le \sum _{m=1}^{n}m\frac{R\left(mx\right)}{mx}\mathrm{.}}\end{array}$ Itt a bal oldal mindig nemnegatív, a jobb oldalon pedig egy olyan véges összeg áll, amelynek minden tagja 0-hoz tart, hiszen láttuk, hogy $R$ sűrűsége 0. Végeredményben tehát a bal oldal is 0-hoz tart, ami éppen azt jelenti, hogy $R_n$ sűrűsége 0. Ezzel a feladatot megoldottuk.  Frenkel Péter (Fazekas M. Főv. Gyak. Gimn., III. o. t.)   Megjegyzés. A tarkaság és a feladatban felvetett probléma más $s$ alapú számrendszerekben is megfogalmazható: mind a két módszer igazolja ebben az általános esetben is $n$-tarka számok létezését, továbbá hogy $s\ge 3$ mellett tarka számok nincsenek. A kettes számrendszerben ellenben minden páros szám tarka, hiszen a többszörösei 1-gyel kezdődnek és ‐ párosak lévén ‐ 0-ra végződnek.