A B. 4202. feladat (2009. október)

B. 4202. Egy papírlapra felírtuk a számokat 1-től 2009-ig. A második lépésben mindegyik szám kétszeresét is felírtuk a papírra, majd kiradíroztuk azokat a számokat, amelyek kétszer is szerepeltek. Ezt a lépést ismételgetjük olyan módon, hogy az i-edik lépésben a papíron éppen látható számok mindegyikének i-szeresét is felírjuk a papírra, majd kiradírozzuk azokat a számokat, amelyek kétszer is szerepelnek. Bizonyítsuk be, hogy a papírlapon minden lépés után legalább 2009 szám lesz.

(5 pont)

A beküldési határidő 2009. november 10-én LEJÁRT.

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.

Statisztika:

29 dolgozat érkezett.
5 pontot kapott:	É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 pontot kapott:	1 versenyző.
0 pontot kapott:	17 versenyző.

A KöMaL 2009. októberi matematika feladatai