I am trying to solve a problem which is a simple algorithmic game.
Link to the problem - https://community.topcoder.com/stat?c=problem_statement&pm=6856
I have basically figured out that for each possible position (number of coins) I need to find whether its a winning state or losing state.
I also know that the this sequence of Ws and Ls is having a periodic behavior. I just want to know how can I find the period given a set of moves ?
The sequence of isn’t necessarily periodic: it’s eventually periodic. That is, the periodic part may start after a non-empty initial segment. Consider the subtraction set $\{3,5,9\}$. I’ll use $W$ for a position in which the person whose turn it is can win, and $L$ for a position in which the person whose turn it is has no winning move. (This may be the opposite of your usage: with my convention the coding problem asks you to determine the number of positions up to some maximum that evaluate to $L$, meaning that the first player must lose if the second player plays correctly.)
$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ \text{Value}:&L&L&L&W&W&W&W&W&L&W&W&W&L&W&L\\ \hline n:&15&16&17&18&19&20&21&22&23&24&25&26&27&28&29\\ \text{Value}:&W&L&W&L&W&L&W&L&W&L&W&L&W&L&W \end{array}$$
Of course $n$ has the value $W$ if and only if at least one of $n-3,n-5$, and $n-9$ has the value $L$, and $n$ has the value $L$ if and only if all of $n-3,n-5$, and $n-9$ have the value $W$, so it’s easy to extend the table recursively. It appears that the sequence of values is eventually alternating between $W$ and $L$, with an initial string of values that don’t fall into this pattern, but how can I be sure that the alternation will now continue forever?
I’ll write $v_n$ for the value ($W$ or $L$) of the position $n$. Suppose that I find an $m\in\Bbb N$ such that $v_{m+k}=v_{m+9+k}$ for $k=0,\ldots,8$; this is just saying that the $9$-tuples of values
$$\langle v_m,v_{m+1},v_{m+2},v_{m+3},v_{m+4},v_{m+5},v_{m+6},v_{m+7},v_{m+8}\rangle$$
and
$$\langle v_{m+9},v_{m+10},v_{m+11},v_{m+12},v_{m+13},v_{m+14},v_{m+15},v_{m+16},v_{m+17}\rangle$$
are identical. Because $\max\{3,5,9\}=9$, the values in the second of these $9$-tuples are completely determined by the values in the first of these $9$-tuples. An easy induction argument now shows that the $9$-tuples
$$\langle v_{m+9k},v_{m+9k+1},v_{m+9k+2},v_{m+9k+3},v_{m+9k+4},v_{m+9k+5},v_{m+9k+6},v_{m+9k+7},v_{m+9k+8}\rangle$$
for $k\in\Bbb N$ will all be equal.
In this example we see that we can take $m=11$: the $9$ values $v_{11}$ through $v_{19}$ are identical to the next $9$ values, $v_{20}$ through $v_{28}$, so we’ve established that the sequence of values repeats starting at $v_{11}$. The initial segment $\langle v_0,\ldots,v_{10}\rangle$, however, cannot be fitted into the periodic tail of the sequence.
(If you’re familiar with Sprague-Grundy values, you may want to compare the sequence of them with the sequence of $W$ and $L$ values: it’s
$$\langle 0,0,0,1,1,1,2,2,0,3,3,1,0,2,\color{red}{0,1,0,1,0,1,\ldots}\rangle\;,$$
so it doesn’t actually start until $n=14$.)
You can use the discussion of this example to see how to tell when you’ve found the repeating part of the sequence. The basic idea is to generate the value sequence recursively until you have identical consecutive segments of length $\max X$, where $X$ is the set of legal moves. After that it’s just a bit of arithmetic.
You may find this PDF of interest.