There are two piles with $72$ and $30$ candies. Two students alternate taking candies from one of the piles. Each time the number of candies taken from a pile must be a multiple of the number of candies in the other pile. Which student can always assure taking the last candy from one of the piles?
Problem
Source:
Tags: floor function
mavropnevma
05.01.2014 02:37
If the two piles have $n>m\geq 0$ candies, we call this a winning position if the player whose turn is to play has a winning strategy; in particular, for $m=0$, the position is losing, since the other player has won. For $m>0$, let $k = \lfloor n/m\rfloor$. If $k>1$ then either $m > n-km$ is losing, or else $n - (k-1)m > m$ is losing (since it forces the other player to move to the winning $m > n-km$ position), so $n>m$ is winning. Therefore any $n\geq 2m$ position is winning. Thus $(72, 30)$ is winning (for the first player). If any precise set of moves is wanted, it will be $(72,30)\longrightarrow (42,30) \implies (30,12) \longrightarrow (18,12) \implies (12,6)\longrightarrow (6,0)$, where $\implies$ means a forced move. Notice that for $k=1$ we don't immediately know who wins. For example $(3,2)$ is obviously losing, but $(5,3)$ is winning.