Problem B. 4192. (September 2009)

B. 4192. The numbers 1 to 2009 are written on a sheet of paper. Then the double of each number is also written on it. Finally, all those numbers are erased that occur twice. This procedure is repeated in the following way: In the ith step, i times the numbers are written on the sheet, and all those numbers are erased that occur twice. How many numbers will be on the sheet after 2009 steps?

(4 pont)

Deadline expired on October 12, 2009.

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

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.

Statistics:

136 students sent a solution.
4 points:	63 students.
3 points:	29 students.
2 points:	21 students.
1 point:	5 students.
0 point:	18 students.

Problems in Mathematics of KöMaL, September 2009