## Le Monde puzzle [#950]

**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, 8pilesof 3, 7pilesof 4, and 4pilesof 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

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)}

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

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)}

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.)

## Leave a Reply