## Le Monde puzzle [#1019]

**A** gamey (and verbose) Le Monde mathematical puzzle:

A two-player game involves n+2 cards in a row, blue on one side and red on the other. Each player can pick any blue card among the n first ones and flip it plus both following ones. The game stops when no blue card is left to turn. The gain for the last player turning cards is 20-t, where t is the number of times cards were flipped, with gain t for its opponent. Both players aim at maximising their gain.

1. When n=4 and all cards are blue, can the first player win? If not, what is the best score for this player?

2. Among all 16 configurations at start, how many lead to the first player to win?

3. When n=10 and all cards are blue, how many cards are flipped an odd number of times for the winning configuration?

The first two questions can easily be processed by an R code like the following recursive function:

liplop <- function(x,n,i){ if (max(x[1:n])==0){ return(i) }else{ sol=NULL for (j in (1:n)[x[1:n]==1]){ y=x;y[j:(j+2)]=1-y[j:(j+2)] sol=c(sol,20-liplop(y,n,i+1))} return(max(sol))}}

Returning

> liplop(rep(1,6),4,0) [1] 6

Meaning the first player cannot win, by running at most six rounds. Calling the same function for all 4⁴=16 possible configurations leads to 8 winning ones:

[1] 0 0 0 1 [1] 0 0 1 1 [1] 0 1 0 1 [1] 0 1 1 1 [1] 1 0 0 0 [1] 1 0 1 0 [1] 1 1 0 0 [1] 1 1 1 0

Solving the same problem with n=10 is not feasible with this function. (Even n=6 seems out of reach!)

## Leave a Reply