KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem C. 1231. (May 2014)

C. 1231. Consider those \(\displaystyle n\)-digit natural numbers that have no digits different from 1 and 2. Prove that there is a number among them that is divisible by \(\displaystyle 2^n\).

(5 pont)

Deadline expired on 10 June 2014.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

51 students sent a solution.
5 points:Á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 points:Bekő Zsófia, Knoch Júlia, Mátyus Adrienn, Somogyi Pál, Szemerédi Levente, Uzonyi 000 Ákos, Varsányi András.
3 points:5 students.
2 points:3 students.
1 point:3 students.
0 point:3 students.
Unfair, not evaluated:1 solution.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley