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, 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

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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s