## Le Monde puzzle [#860]

Posted in Books, Kids, R with tags , , , , on April 4, 2014 by xi'an

A Le Monde mathematical puzzle that connects to my awalé post of last year:

For N≤18, N balls are placed in N consecutive holes. Two players, Alice and Bob, consecutively take two balls at a time provided those balls are in contiguous holes. The loser is left with orphaned balls. What is the values of N such that Bob can win, no matter what is Alice’s strategy?

I solved this puzzle by the following R code that works recursively on N by eliminating all possible adjacent pairs of balls and checking whether or not there is a winning strategy for the other player.

```topA=function(awale){
# return 1 if current player can win, 0 otherwise

best=0
if (max(awale[-1]*awale[-N])==1){

for (i in (1:(N-1))[awale[1:(N-1)]==1]){

if (awale[i+1]==1){
bwale=awale
bwale[c(i,i+1)]=0
best=max(best,1-topA(bwale))
}
}}
return(best)
}

for (N in 2:18) print(topA(rep(1,N)))
```

which returns the solution

```[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
[1] 1
[1] 1
[1] 0
[1] 1
[1] 1
[1] 1
<pre>```

(brute-force) answering the question that N=5,9,15 are the values where Alice has no winning strategy if Bob plays in an optimal manner. (The case N=5 is obvious as there always remains two adjacent 1’s once Alice removed any adjacent pair. The case N=9 can also be shown to be a lost cause by enumeration of Alice’s options.)

## awalé

Posted in Kids, pictures, R with tags , , , on May 13, 2013 by xi'an

Following Le Monde puzzle #810, I tried to code an R program (not reproduced here) to optimise an awalé game but the recursion was too rich for R:

```Error: evaluation nested too deeply:
infinite recursion / options(expressions=)?
```

even with a very small number of holes and seeds in the awalé… Searching on the internet, it seems the computer simulation of a winning strategy for an awalé game still is an open problem! Here is a one-step R function that does  not produce sure gains for the first player, far from it, as shown by the histogram below…  I would need a less myopic strategy by iterating  this function at least twice.

```onemorestep=function(x,side){
# x current state of the awale,
# side side of the awale (0 vs 1)

M=length(x);N=as.integer(M/2)
rewa=rep(0,M)
newb=matrix(0,ncol=M,nrow=M)

for (i in ((1:N)+N*side)){

if (x[i]>0){
y=x
y[i]=0
for (t in 0:(x[i]-1))
y[1+(i+t)%%M]=y[1+(i+t)%%M]+1

last=1+(i+t)%%M
if (side){ gain=(last<=N)
}else{ gain=(last>N)}

if (gain){# ending up on the right side
rewa[i]=0
while (((last>0)&&(side))||((last>N)||(!side)))
if ((y[last]==2)||(y[last]==3)){
rewa[i]=rewa[i]+y[last];y[last]=0
last=last-1
}else{ break()}
}
newb[i,]=y
}
}
if (max(rewa)>0){
sol=order(-rewa)[1]
}else{ sol=rang=((1:N)+N*side)[x[((1:N)+N*side)]>0]
if (length(rang)>1) sol=sample(rang,1,prob=x[rang]^3)}

return(list(reward=max(rewa),board=newb[sol,]))
}
```

## interesting puzzle

Posted in Books, Kids, R with tags , , , , , on April 25, 2013 by xi'an

In addition to its weekly mathematics puzzles, Le Monde is now publishing a series of vulgarisation books on mathematics, under the patronage of Cédric Villani. Jean-Michel Marin brought me two from the series, one on the golden number and one on Pythagoras’ theorem. (This is actually a translation of a series published by El Pais last year.) Those books are a bit stretched given the topic, even though I enjoyed the golden number (the second one having a lot of redundancy with the first one.) However, I came upon an interesting question, namely about the maximum size of a cube that could fit through a tunnel drilled through the unit cube. Sadly, I could not find an answer to this problem on the web, even though the book mentions a solution with a side larger than one…

## Le Monde puzzle [#810]

Posted in Books, Kids, R with tags , , , , , on March 6, 2013 by xi'an

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