A Le Monde mathematical puzzle with Alice and Bob:
Alice and Bob play a game with 100 tokens set in ten piles of 1, 9 piles of 2, 8 piles of 3, 7 piles of 4, and 4 piles of 5. They each take a token in turn, either to remove it from the game, or to create a new pile of one, provided this token is taken from a pile with at least two remaining tokens. The winner is the one left with the last token. If Alice starts, who is the winner?
I just wrote a most rudimentary recursive R function
[sourcecode language=”r” gutter=”false”]
reward=function(tokens){
gain=0
if (max(tokens)>0){
#takes one token off
for (i in (1:5)[tokens>0]){
gain=max(gain,1-reward(tokens-((1:5)==i)))
if (gain==1) break()}
#create another singleton
if (max(tokens[-1])>1){
for (i in (2:5)[tokens[-1]>1]){
gain=max(gain,1-reward(c(tokens[1]+1,tokens[-1]-((2:5)==i))))
if (gain==1) break()}}}
return(gain)}
[/sourcecode]
where token represents the number of remaining sets with 1, 2, 3, 4, and 5 tolkiens. With the suggested values, (10,18,24,28,20), the R code takes too long on my machine! Or even overnight on our server. So as usual I thought a bit more about it and started cutting at unnecessary bits, reaching the faster recursive function
[sourcecode language=”r” gutter=”false”]
reward=function(tokens){
#clean up piles with single token
tokens[1]=tokens[1]+sum((tokens[-1]==1))
tokens[-1][tokens[-1]==1]=0
if (max(tokens[-1])==0){
#end: no choice left
gain=1*(tokens[1]%%2==1)
}else{
gain=0
#all piles have to disappear, order should not matter
i=min((2:5)[tokens[-1]>1])
#set one token appart
gain=max(gain,1-reward(tokens-((1:5)==i)))
#create another singleton
gain=max(gain,1-reward(c(tokens[1]+1,tokens[-1]-((2:5)==i))))}
return(gain)}
[/sourcecode]
as all sets have to vanish at one point or another so order should not matter. However, with the starting values provided in the puzzle, two weeks of computation on our local cluster did produce nothing, as there are too many cases to examine! (The exact solution is that Alice cannot win the game if Bob plays in an optimal manner.)
