A C. 1231. feladat (2014. május)

C. 1231. Igazoljuk, hogy azok között az $\displaystyle n$ jegyű természetes számok között, amelyek számjegyei kizárólag 1 és 2 közül kerülnek ki, van olyan, amelyik osztható $\displaystyle 2^n$-nel.

(5 pont)

A beküldési határidő 2014. június 10-én LEJÁRT.

Megoldás. Vizsgáljunk meg néhány esetet. Ha $\displaystyle n=1$, akkor 2|2. Ha $\displaystyle n=2$, akkor $\displaystyle 4|12=4\cdot3$. Ha $\displaystyle n=3$, akkor $\displaystyle 8|112=8\cdot14$. Ha $\displaystyle n=4$, akkor $\displaystyle 16|2112=16\cdot132$. Megfigyelhető, hogy mindig az előző szám elé került egy 1-es vagy egy 2-es. Bizonyítsuk az állítást teljes indukcióval. $\displaystyle n=1$-re már láttuk, hogy igaz. Tegyük fel, hogy az állítás igaz $\displaystyle n=k$-ra, vagyis $\displaystyle 2^k|m$, ahol $\displaystyle m$ egy $\displaystyle k$-jegyű, csupa 1-esből és 2-esből álló szám. Ekkor $\displaystyle m$ maradéka $\displaystyle 2^{k+1}$-gyel osztva vagy 0, vagy $\displaystyle 2^k$. Ha 0, akkor a szám elé egy 2-est írva, azt $\displaystyle 2\cdot10^k$-nal növeljük. Mivel $\displaystyle 2\cdot10^k=2\cdot2^k\cdot5^k=2^{k+1}\cdot5^k$, így $\displaystyle m$-et egy $\displaystyle 2^{k+1}$-nel osztható számmal növeljük, így a kapott szám is osztható lesz $\displaystyle 2^{k+1}$-nel. Ha pedig $\displaystyle m$ maradéka $\displaystyle 2^{k+1}$-gyel osztva $\displaystyle 2^k$, akkor az $\displaystyle m$ szám elé egy 1-est írva, azt $\displaystyle 10^k$-nal növeljük meg. Mivel $\displaystyle 10^k=2^k\cdot5^k$, és $\displaystyle 5^k=2s+1$, ahol $\displaystyle s$ pozitív egész szám, így $\displaystyle 10^k=2^k\cdot(2s+1)=2^{k+1}\cdot s+2^k$, vagyis $\displaystyle 10^k$ szintén $\displaystyle 2^k$-t ad maradékul $\displaystyle 2^{k+1}$-nel osztva, így a kapott $\displaystyle k+1$-jegyű szám maradéka $\displaystyle 2^{k+1}$-nel osztva $\displaystyle 2^k+2^k=2^{k+1}$, vagyis a szám osztható $\displaystyle 2^{k+1}$-nel. Tehát az állítás igaz $\displaystyle n=k+1$-re, a bizonyítást befejeztük.

Statisztika:

51 dolgozat érkezett.
5 pontot kapott:	Árvai Balázs, Balázs Ákos Miklós, Bottlik Judit, Döbröntei Dávid Bence, Gáspár Attila, Horváth 016 Gábor, Kasó Ferenc, Kerekes Anna, Klász Viktória, Kovács 162 Viktória, Kovács 246 Benedek, Kovács Péter Tamás, Matusek Márton, Mihálykó Péter, Molnár-Sáska Zoltán, Németh 123 Balázs, Pap-Takács Mónika, Polgár Márton, Radnai Bálint, Ratkovics Gábor, Regős Krisztina, Sebastian Fodor, Somlyay Anna, Szécsényi Nándor, Szécsi Adél Lilla, Széles Katalin, Tompa Tamás Lajos, Várkonyi Dorka, Zsakó Ágnes.
4 pontot kapott:	Bekő Zsófia, Knoch Júlia, Mátyus Adrienn, Somogyi Pál, Szemerédi Levente, Uzonyi 000 Ákos, Varsányi András.
3 pontot kapott:	5 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	3 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2014. májusi matematika feladatai