A B. 4192. feladat (2009. szeptember)

B. 4192. 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 az 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. Hány szám lesz a papírlapon a 2009. lépés után?

(4 pont)

A beküldési határidő 2009. október 12-én LEJÁRT.

Megoldás. Az eljárást úgy is elvégezhetjük, hogy először minden $\displaystyle 1\le i\le 2009$ és $\displaystyle 1\le k\le 2009$ esetén az $\displaystyle ik$ számot felírjuk a papírlapra, majd tetszés szerint kiradírozunk két azonos számot, és ezt a lépést addig ismételgetjük, amíg csak lehet. Ha $\displaystyle 1\le i<k\le 2009$ esetén az $\displaystyle ik$ számot felírtuk a papírlapra, akkor ugyanezt a számot $\displaystyle ki$ alakban is felírtuk. A kiradírozást végezzük el olyan sorrendben, hogy minden egyes lépésben egy így létrejött párt radírozunk ki. Világos, hogy az eljárás végén azok az $\displaystyle ik$ alakú számok maradnak meg, amelyekre $\displaystyle 1\le i=k\le 2009$. Vagyis pontosan 2009 szám marad a papíron, nevezetesen az első 2009 négyzetszám.

Statisztika:

136 dolgozat érkezett.
4 pontot kapott:	63 versenyző.
3 pontot kapott:	29 versenyző.
2 pontot kapott:	21 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	18 versenyző.

A KöMaL 2009. szeptemberi matematika feladatai