## Le Monde puzzle [#950]

Posted in Books, Kids, pictures, Statistics, Travel, University life with tags , , , , on March 10, 2016 by xi'an

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

## Le Monde puzzle [#930]

Posted in Books, Kids, Statistics, University life with tags , , , on October 9, 2015 by xi'an

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.

## Le Monde puzzle [#910]

Posted in Books, Kids, Statistics, University life with tags , , on May 8, 2015 by xi'an

An game-theoretic Le Monde mathematical puzzle:

A two-person game consists in choosing an integer N and for each player to successively pick a number in {1,…,N} under the constraint that a player cannot pick a number next to a number this player has already picked. Is there a winning strategy for either player and for all values of N?

for which I simply coded a recursive optimal strategy function:

```gain=function(mine,yours,none){
fine=none
if (length(mine)>0)
fine=none[apply(abs(outer(mine,none,"-")),
2,min)>1]
if (length(fine)>0){
rwrd=0
for (i in 1:length(fine))
rwrd=max(rwrd,1-gain(yours,c(mine,fine[i]),
none[none!=fine[i]]))
return(rwrd)}
return(0)}
```

which returned a zero gain, hence no winning strategy for all values of N except 1.

```> gain(NULL,NULL,1)
[1] 1
> gain(NULL,NULL,1:2)
[1] 0
> gain(NULL,NULL,1:3)
[1] 0
> gain(NULL,NULL,1:4)
[1] 0
```

Meaning that the starting player is always the loser!

## Le Monde puzzle [#905]

Posted in Books, Kids, R, Statistics, University life with tags , , , on April 1, 2015 by xi'an

A recursive programming  Le Monde mathematical puzzle:

Given n tokens with 10≤n≤25, Alice and Bob play the following game: the first player draws an integer1≤m≤6 at random. This player can then take 1≤r≤min(2m,n) tokens. The next player is then free to take 1≤s≤min(2r,n-r) tokens. The player taking the last tokens is the winner. There is a winning strategy for Alice if she starts with m=3 and if Bob starts with m=2. Deduce the value of n.

Although I first wrote a brute force version of the following code, a moderate amount of thinking leads to conclude that the person given n remaining token and an adversary choice of m tokens such that 2m≥n always win by taking the n remaining tokens:

```optim=function(n,m){

outcome=(n<2*m+1)
if (n>2*m){
for (i in 1:(2*m))
outcome=max(outcome,1-optim(n-i,i))
}
return(outcome)
}
```

eliminating solutions which dividers are not solutions themselves:

```sol=lowa=plura[plura<100]
for (i in 3:6){
sli=plura[(plura>10^(i-1))&(plura<10^i)]
ace=sli-10^(i-1)*(sli%/%10^(i-1))
lowa=sli[apply(outer(ace,lowa,FUN="=="),
1,max)==1]
lowa=sort(unique(lowa))
sol=c(sol,lowa)}
```

which leads to the output

```> subs=rep(0,16)
> for (n in 10:25) subs[n-9]=optim(n,3)
> for (n in 10:25) if (subs[n-9]==1) subs[n-9]=1-optim(n,2)
> subs
[1] 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
> (10:25)[subs==1]
[1] 18
```

Ergo, the number of tokens is 18!

## 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){
#there are adjacent balls remaining

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