Feladat:	C.1432	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Agócs Katinka ,  Ajtai Boglárka ,  Balog Lóránd ,  Bíró Dániel ,  Bukor Benedek ,  Deák Péter ,  Dékány Barnabás ,  Havlik Miklós ,  Horváth Dávid ,  Jankovits András ,  Julinek István ,  Kiszelovics Dorina ,  Mészáros Márton ,  Molnár István ,  Németh Csilla Márta ,  Porkoláb Mercédesz ,  Rittgasszer Ákos ,  Spányik Teodor ,  Surján Anett ,  Szántó Julianna ,  Szécsi Adél Lilla ,  Szepessy Luca ,  Szőnyi Laura ,  Tóth Imre
Füzet:	2017/december, 535 - 536. oldal		PDF  |  MathML
Témakör(ök):	C gyakorlat, Oszthatóság, Számjegyekkel kapcsolatos feladatok
Hivatkozás(ok):	Feladatok: 2017/szeptember: C.1432

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. Úgy látjuk be az állítás helyességét, hogy megadunk egy ,,algoritmust'' egy ilyen $n$-jegyű szám elkészítéséhez. Nézzük meg az első néhány megoldást: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{ccccc}\hfill {\displaystyle n}& {\displaystyle =1}\hfill & {\displaystyle \to }\hfill & \hfill {\displaystyle 2}& {\displaystyle =2\cdot 1;}\hfill \\ \hfill {\displaystyle n}& {\displaystyle =2}\hfill & {\displaystyle \to }\hfill & \hfill {\displaystyle 12}& {\displaystyle =2^2\cdot 3;}\hfill \\ \hfill {\displaystyle n}& {\displaystyle =3}\hfill & {\displaystyle \to }\hfill & \hfill {\displaystyle 112}& {\displaystyle =2^3\cdot 14;}\hfill \\ \hfill {\displaystyle n}& {\displaystyle =4}\hfill & {\displaystyle \to }\hfill & \hfill {\displaystyle 2112}& {\displaystyle =2^4\cdot 132;}\hfill \\ \hfill {\displaystyle n}& {\displaystyle =5}\hfill & {\displaystyle \to }\hfill & \hfill {\displaystyle 22112}& {\displaystyle =2^5\cdot 691;}\hfill \\ \hfill {\displaystyle n}& {\displaystyle =6}\hfill & {\displaystyle \to }\hfill & \hfill {\displaystyle 122112}& {\displaystyle =2^6\cdot 1908.}\hfill \end{array}}}\end{array}$ Megfigyelhető a következő szabályszerűség: ha a $2^n$-nel való osztás eredménye páratlan szám, akkor 1-es, ha pedig páros szám, akkor 2-es számjegy kerül az előző szám elé. Bebizonyítjuk, hogy ha továbbra is ezt az eljárást követjük, akkor a keletkező $n+1$-jegyű szám mindig osztható lesz $2^{n+1}$-nel. $n\ge 6$ esetén az előzőleg már megkapott $n$-jegyű szám $2^n$-nel való osztásakor vagy páratlan, vagy páros számot kapunk. I. eset: páratlan számot kapunk. Ekkor írjunk 1-et a szám elé. Az új szám $A=({10}^n+n$-jegyű szám) alakú, vagyis $\begin{array}{c}{\displaystyle A=2^n\cdot 5^n+2^n\left(2l+1\right)=2^n\left(5^n+2l+1\right)\mathrm{.}}\end{array}$ Mivel $5^n+2l+1$ páros szám, ezért $2^{n+1}\mid A$ teljesül. II. eset: páros számot kapunk. Ekkor írjunk 2-est a szám elé. Az új szám ekkor $B=(2\cdot {10}^n+n$-jegyű szám) alakú: $\begin{array}{c}{\displaystyle B=2\cdot 2^n\cdot 5^n+2^n\cdot 2k=2^n\left(2\cdot 5^n+2k\right)\mathrm{.}}\end{array}$ Mivel $2\cdot 5^n+2k$ páros szám, ezért $2^{n+1}\mid B$ teljesül. Adtunk egy eljárást, amellyel minden $n$ pozitív egész szám esetén készíthető olyan $2^n$-nel osztható $n$-jegyű szám, amelynek számjegyei kizárólag 1-esből és 2-esből állnak.   II. megoldás. $2^n$ darab olyan $n$-jegyű szám van, amely csak 1-esből és 2-esből áll (mert minden helyiértékre két szám közül választhatunk). Az összes ilyen $n$-jegyű számot elosztva rendre $2^n$-nel legfeljebb $2^n$ darab különböző maradékot kaphatunk az osztás eredményeként (éspedig: $0;1;2;\text{...};2^n-1$). Belátjuk, hogy minden ilyen $n$-jegyű szám különböző maradékot ad $2^n$-nel osztva. Indirekt módon tegyük fel, hogy van két különböző, csak 1-esből és 2-esből álló $n$-jegyű szám, amely ugyanazt a maradékot adja $2^n$-nel osztva. Így a két szám különbsége (a nagyobbikból a kisebbet kivonva) osztható lesz $2^n$-nel. Ez a különbség legfeljebb $n$-jegyű szám lehet, melynek az ,,első'' nem 0 számjegye (az 1-es helyiértéktől indulva a nagyobbak felé) vagy 1-es (a $2-1$ miatt), vagy 9-es (az $1-2$ miatt). Így ez a különbségként kapott szám $A\cdot {10}^k$ alakú lesz, ahol $A$ egy páratlan természetes szám, míg $k$ a 0-k száma az (1-es helyiértéktől indulva) első 1-es vagy 9-es jegyig. Mivel a különbség legfeljebb $n$-jegyű, a fentiek alapján legfeljebb $\left(n-1\right)$ darab 0-ra végződhet, azaz a különbség legfeljebb $2^{n-1}$-gyel osztható (hiszen ${10}^{n-1}=2^{n-1}\cdot 5^{n-1}$). Ellentmondáshoz jutottunk, tehát nincs két olyan különböző, csak 1-esből és 2-esből álló $n$-jegyű szám, amely ugyanazt a maradékot adja a $2^n$-nel való osztásnál. Vagyis minden maradék különböző. Figyelembe véve, hogy pontosan $2^n$ darab, a feltételeknek megfelelő $n$-jegyű szám van, így pontosan $2^n$ darab különböző maradékunk van, vagyis van (pontosan egy darab) olyan $n$-jegyű szám, amely csupa 1-esből és 2-esből áll és $2^n$-nel való osztási maradéka 0 $-$ és ezt akartuk bizonyítani.