Le Monde puzzle [#905]

(This article was originally published at Xi'an's Og » R, and syndicated at StatsBlogs.)

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!

Please comment on the article here: Xi'an's Og » R

Tags: books, Kids, Le Monde, mathematical puzzle, R, recursive function, statistics, University life