Problem B. 4202. (October 2009)

B. 4202. The numbers 1 to 2009 are written on a sheet of paper. In the second step, the double of each number is also written on the sheet and then all those numbers are erased that occur twice on it. This step is repeated as follows: in step i, every number on the sheet is multiplied by i, the results are written down and then all those numbers are erased that occur twice. Prove that there will be at least 2009 numbers on the sheet after every step.

(5 pont)

Deadline expired on November 10, 2009.

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

Megoldás. Az első lépés után pontosan \(\displaystyle k=2009\) szám van a papíron. A második lépés után az 1 és \(\displaystyle k\) közötti páratlan számok, valamint a \(\displaystyle k+1=2010\) és a \(\displaystyle 2k=4018\) közötti páros számok szerepelnek a papíron, ez összesen 2010 szám. Nézzük meg, hogy a harmadik lépés után hány olyan szám lesz a papíron, amely \(\displaystyle (3k+1)/2\) és \(\displaystyle 6k\) közé esik. Ezek között szerepelnek a \(\displaystyle 3(k+1)\) és \(\displaystyle 6k\) közé eső 6-tal osztható számok, melyeket a harmadik lépésben írunk fel, de a második lépés után még nem szerepelnek a papíron, ez összesen 1005 darab szám. Szerepelni fognak a \(\displaystyle (3k+1)/2\) és \(\displaystyle 2k\) közé eső páros számok is, mert ezek a második lépés után fent vannak a papíron, de a harmadik lépésben nem írjuk fel őket újra, ez 503 darab szám. Végül szerepelni fognak a \(\displaystyle (3k+1)/2\) és \(\displaystyle 3k\) közé eső 3-mal osztható páratlan számok is, melyek a harmadik lépésben kerülnek fel először a papírra, ezek száma ugyancsak 503.

Vagyis \(\displaystyle n=3\) esetén igaz lesz, hogy az \(\displaystyle n.\) lépés után a papíron szerepel 2011 darab olyan \(\displaystyle N\) szám, amelyre

\(\displaystyle \frac{n!k}{4}<N\le n!k.\)

Ez az állítás minden \(\displaystyle n\ge 3\) esetén érvényben marad, ugyanis az \(\displaystyle n.\) lépés után a papíron szereplő legnagyobb szám \(\displaystyle n!k\), és ha valamely \(\displaystyle N\) számra a fenti egyenlőtlenség teljesül, akkor az \(\displaystyle (n+1).\) lépésben felért \(\displaystyle (n+1)N\) számra

\(\displaystyle n!k\le \frac{n+1}{4}\cdot {n!k}=\frac{(n+1)!k}{4}< (n+1)N \le (n+1)!k,\)

ami azt is maga után vonja, hogy ez a szám az \(\displaystyle n.\) lépés után még nem szerepelt a papíron.

Az állítás tehát könnyen igazolható \(\displaystyle n\) szerinti teljes indukcióval, és azt mutatja, hogy a harmadik lépést követően a papíron mindig lesz legalább 2011 szám.

Statistics:

29 students sent a solution.
5 points:	Éles András, Gyarmati Máté, Karkus Zsuzsa, Korondi Zénó, Mester Márton, Mészáros András, Perjési Gábor, Strenner Péter, Weisz Ágoston, Weisz Gellért, Zsakó András.
1 point:	1 student.
0 point:	17 students.

Problems in Mathematics of KöMaL, October 2009