Problem B. 4892. (September 2017)

B. 4892. Two players, First and Second, play the following game: they place 2017 pebbles on the table. First starts by removing 1 pebble. Then Second may choose to remove either 1 or 2. Then First may remove 1, 2, 3 or 4. Then Second may remove any number from 1 to 8. And so on, the player in the \(\displaystyle i\)th step needs to remove at least 1 and at most \(\displaystyle 2^{i-1}\) pebbles. The player removing the last pebble from the table wins the game. Who has a winning strategy?

(6 pont)

Deadline expired on October 10, 2017.

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

Megoldás. Az első 10 lépés alatt elvehető kavicsok száma legfeljebb \(\displaystyle 1+2+4+\dots+512=1023\), így ennyi lépés után még biztosan nem ér véget a játék. A 11. lépésben Kezdő legfeljebb 1024 kavicsot vehet el, vagyis akkor tud ebben a lépésben nyerni, ha az első 10 lépés során elvett kavicsok száma legalább 993. Azonban ezt Második meg tudja akadályozni, például úgy, hogy az első 5 lépése során mindig csak egy-egy kavicsot vesz el. így ugyanis az első 10 lépés alatt elvett kavicsok száma biztosan nem lesz több, mint \(\displaystyle 1+1+4+1+16+1+64+1+256+1=346\). Vagyis Második el tudja érni, hogy a 11. lépés után még legyen kavics. Mivel Második a 12. lépésben (ami az ő 6. lépése) akár 2048 kavicsot is elvehetne, így csak annyit kell tennie, hogy az összes még az asztalon lévő kavicsot elveszi, és ezzel megnyeri a játékot. Tehát beláttuk, hogy Másodiknak van nyerő stratégiája.

Statistics:

183 students sent a solution.
6 points:	152 students.
5 points:	21 students.
4 points:	4 students.
3 points:	1 student.
2 points:	1 student.
1 point:	1 student.
0 point:	3 students.

Problems in Mathematics of KöMaL, September 2017