Le Monde puzzle [#810]

March 5, 2013
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

The current puzzle is as follows:

Take a board with seven holes and seeds. The game starts with one player putting the seeds on the holes as he or she wishes. The other player picks a seed wherever. Then, alternatively, each player picks a seed in a hole contiguous to the previous one. The loser is the one finding only empty holes to pick from. Who is the winner with 28? 29? 30 seeds?

This is a simplified version of the awalé or oware we used to play with my kids.

I first defined a recursive function on the win/loose value of a particular location, based on the assumption that each player was picking the best location at each step:

f=function(x,i){
 if (x[i]==0){# losing location
    v=0;return(v)}else{

   if ((i>1)&&(i<7)){
     x[i]=x[i]-1;return(1-max(f(x,i-1),f(x,i+1)))
     }else{

       if (i==1){ x[i]=x[i]-1;return(1-f(x,2))}
       if (i==7){ x[i]=x[i]-1;return(1-f(x,6))}
       }
}}

and then checked whether or not winning solutions were available for 28, 29, and 30 seeds dropped at random:

N=28 #number of seeds
glosol=1  #boolean
for (t in 1:10^3){#random starts

  seeds=sample(1:7,N,rep=TRUE)
  x=rep(0,7)
  for (i in 1:7) x[i]=sum(seeds==i)

  sol=i=0 #second player result
  while ((i<7)&&(sol==0)){
        i=i+1;sol=f(x,i)}
  if (sol==0){ #winning configuration for first player
    glosol=0;print(x);break()}
  }

getting solutions for 28 (5 6 2 3 5 5 2) and 30 (6 6 2 4 4 5 3), but none for 29.

Actually, the rule seems to be that odd numbers get no solutions and even numbers get solutions (e.g., 1 1 1 1 1 2 1 for 8 seeds). (This means further that to build a winning allocation for 2N seeds, we only need to take a configuration at random with 2N+1 seeds and check which seed we need to remove to get a winning (for the “other” player) configuration.)


Filed under: Books, Kids, R Tagged: awalé, Le Monde, mathematical puzzle, oware, R, seeds

To leave a comment for the author, please follow the link and comment on his blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.