Feladat:	F.3084	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Szobonya László ,  Terpai Tamás ,  Visontai Mirkó
Füzet:	1996/február, 97. oldal		PDF  |  MathML
Témakör(ök):	Maradékos osztás, Feladat
Hivatkozás(ok):	Feladatok: 1995/október: F.3084

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. Konstruálunk egy $a_1$, $a_2$, $\text{...}$ sorozatot, amely olyan pozitív egészekből fog állni, amelyeknek a tízes számrendszerbeli felírásai csak $1$-es és $2$-es számjegyekből állnak, továbbá minden $k$ pozitív egészre az $a_k$ szám $k$-jegyű lesz és osztható $2^k$-nal. Ennek a sorozatnak a létezéséből következik a feladat állítása. Legyen $a_1=2$; erre az állítás teljesül. Tegyük fel, hogy már definiáltuk $a_k$-t, amely $k$ jegyű és osztható $2^k$-nal. Tekintsük az $x={10}^k+a_k$ és $y=2\cdot {10}^k+a_k$ számokat. Ezek úgy keletkeznek, hogy az $a_k$ jegyei elé írunk még egy számjegyet. Mindkét szám osztható $2^k$-nal, mert $a_k$ és ${10}^k$ is osztható vele. Másrészt $y-x={10}^k=2^k\cdot 5^k$ nem osztható $2^{k+1}$-nel, tehát $x$ és $y$ $2^{k+1}$-nel osztva különböző maradékot adnak. Egy $2^k$-nal osztható szám azonban $2^{k+1}$-nel osztva csak $0$ vagy $2^k$ maradékot adhat, így $x$ és $y$ közül az egyik $2^{k+1}$-nel osztva $2^k$ maradékot ad, a másik pedig osztható vele. Az utóbbit választva $a_{k+1}$-nek, folytatható a sorozat.  Terpai Tamás (Fazekas M. Főv. Gyak. Gimn., I. o. t.)   II. megoldás. Legyen $k$ pozitív egész, és írjuk fel azokat az $k$-jegyű számokat, amelyeknek minden jegye $1$ vagy $2$. $\begin{array}{c}{\displaystyle 111\text{...}\mathrm{111,}111\text{...}\mathrm{112,}111\text{...}\mathrm{121,}\text{...}\mathrm{,}222\text{...}222.}\end{array}$ Azt állítjuk, hogy ezek $2^k$-nal osztva csupa különböző maradékot adnak. Mivel a felsorolt számok és a lehetséges maradékok száma is éppen $2^k$, ebből következik, hogy minden maradék előfordul, következésképpen a $0$ is. Legyen $x$ és $y$ két különböző szám az imént felsoroltak közül. Azt kell bebizonyítanunk, hogy $x-y$ nem osztható $2^k$-nal. Legyen jobbról számolva az $m$-edik az első olyan helyiérték, ahol $x$ és $y$ jegye nem egyezik meg. A két szám különbsége $m-1$ darab $0$-ra végződik, az ezeket közvetlenül megelőző jegye pedig $1$ vagy $9$. Ebből következik, hogy $x-y=p\cdot {10}^{m-1}$, ahol $p$ egy páratlan szám. Mivel $p\cdot {10}^{m-1}$ prímtényezős felbontásában a $2$ kitevője $m-1<k$, a szám nem osztható $2^k$-nal. Ezzel az állítást beláttuk.  Visontai Mirkó (Fazekas M. Főv. Gyak. Gimn., III. o. t.)