Le Monde puzzle [#930]

A game Le Monde mathematical puzzle:

On a linear board of length 17, Alice and Bob set alternatively red and blue tokens. Two tokens of the same colour cannot sit next to one another. Devise a winning strategy for the first player.

In the ‘Og tradition, this calls for a recurrent R code:

game=function(n=17,col=1,tak=rep(0,n)){
   frei=rew=0*tak
   # stopping rule
   if (sum(tak==col)==0){
     frei=(tak==0)}else{
     for (i in (1:n)[tak!=-col])
       frei[i]=(min(abs((1:n)[tak==col]-i))>1)}
   # left positions
   if (sum(frei)>0){
     for (i in (1:n)[frei==1]){
      prop=tak;prop[i]=col
      rew[i]=1-game(n=n,col=-col,tak=prop)}}
   # outcome of best choice
   return(max(rew))}

While I did not run the rudimentary recursive function for n=17, I got a zero return from n=2 till n=12, meaning that the starting player is always going to lose if the other player plays optimally.

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