I don't know if this more mathematics or informatics related, but I think it fits here.
I found the following problem in a university application (it is translated, sorry for mistakes):
"A two player game has a stack of $n$ $(0 < n < 10001)$ coloured tokens (either red or blue) in a pile. The $a_n$ sequence specifies the colours of the tokens in sequence. The players alternate between steps. A step means that the current player takes $k$ peaces of tokens that are the same colour (at least 1). The player who takes the last token wins. Given a sequence of tokens (specified in the $a_n$ sequence), determine if there is a winning strategy for the starting player." (Actually it prints out YES/NO depending on the existence of a winning strategy.)
An example sequence is: R R B B R B R B.
In this case player one could take 1 or 2 red tokens, if player 1 takes 1 red token, player two is forced to take the remaining red token, if player one takes the two red tokens, player two has to take the blue token, and so on.
I am new to these kind of problems, any idea how should I approach this problem?
A "move" goes from game position $\mathbf a=(a_1,a_2,\ldots, a_n)$ $^{1)}$ to either $(a_2,\ldots, a_n)$ or to some $(a_1',a_2,\ldots, a_n)$ with $1\le a_1'<a_1$. A position $\mathbf a$ is lost (or $f(\mathbf a)=-1$) if all these moves lead to won (or $f(\mathbf a)=+1$) positions, and it is won if at least one move leads to a lost position. As boundary condition, we can declare the empty position $()$ is lost, which makes every position of the form $(a_n)$ a win.
How can we determine for $\mathbf a=(a_1,\ldots, a_n)$ if $f(\mathbf a)=\pm1$?
If $a_1=1$, this is easy: By the forced move, $(a_1,\ldots,a_n)$ is simply the opposite of $(a_2,\ldots, a_n)$; $$f(1,a_2,\ldots,a_n)=-f(a_2,\ldots,a_n).$$
If $a_1>1$, we can at least move to either $\mathbf b=(1,a_2,\ldots,a_n)$ or $\mathbf c=(a_2,\ldots, a_n)$. As $f(\mathbf b)=-f(\mathbf c)$, at least one of these is $-1$, s that $f(\mathbf a)=+1$.
We conclude (by induction) that $$ f(\underbrace{1,\ldots, 1}_k, \ge2,\ldots))=(-1)^k$$ and as exceptional case $$ f(\underbrace{1,\ldots, 1}_n)=(-1)^{n+1}.$$
$^{1)}$ Note that I encode a token sequence such as $R R B B R B R B$ as sequence of counts of same-colour tokens, i.e, here as $(2,2,1,1,1,1)$.