The number "3" is written on a board. Ana and Bernardo take turns, starting with Ana, to play the following game. If the number written on the board is $n$, the player in his/her turn must replace it by an integer $m$ coprime with $n$ and such that $n<m<n^2$. The first player that reaches a number greater or equal than 2016 loses. Determine which of the players has a winning strategy and describe it.
Problem
Source: Centroamerican 2016, problem 4
Tags: games, number theory
Packito
22.06.2016 05:58
Ana has the winning strategy 1) The player who writes $2015$ on the board wins. 2) Ana will always choose the smallest number (of the ones she can write) that is divisible by $5$. She will start replacing $3$ with $5$. 3) Then Bernardo will never write a number divisible by $5$ hence he will never write $2015$. If the smallest multiple of $5$ Ana can write is greater than 2016, that means that $2015$ was already written or it was never written. If it was written then Ana was the one who place it on the board then she already won. If it was never written Ana won since Ana won't pass over a multiple of $5$ since she is writting the multiple closer to $n$. Then Bernardo jumped over $2015$ but that means he lost. $Q.E.D$
roughlife
30.08.2016 07:49
Ana has the winning strategy 1) The player who write $2015$ on the board always wins. In same context, player who write $2005$ always wins. and $2015=5\times13\times31$ , $2005=5\times401$ 2) First, Ana start replacing $3$ with $5$. and, Ana will replace the number with the proper multiple of $5$. So Bernado can't take multiple of $5$. 3) If Bernado won't take multiple $13$ or $31$ in the range above $45$, He will lose. Likewise, he will lose if he doesn't take multiple of $401$. 4) However, Bernado can't take $13k$ or $31m$ and $401l$ simultaneously, because $13\times401>2016$. So ana always wins.