## Le Monde puzzle [#1044]

**A **dynamic programming Le Monde mathematical puzzle:

Bob and Alice are playing a game where Alice fills a one-litre bottle from a water fountain, and empties it between four buckets. Bob then empties two of the four buckets. Alice then fills again her bottle and empties it again in the buckets. Alice wins if she manages to fill one bucket after a finite number of steps. What is the maximum capacity of a bucket for Alice to find a winning strategy?

**T**he question sounded too complex to solve by an R code so I somewhat simplified it by deciding that Alice could not allocate any portion of the litre to a bucket but instead only 0,¼,⅓,½,⅔,¾,1. And then looked at a finite horizon to see how much she could fill a bucket when Bob was trying to minimise this amount: a crude R code just took too long for an horizon of 6 steps and hence I tried to reduce the number of calls to my recursive function

solfrak=c(0,.25,.333,.5,.667,.75,1) petifil=function(buck=rep(0,4),hor=3){ #eliminate duplicates albukz=NULL for (a in solfrak) for (b in solfrak[!(solfrak+a>1)]) for (c in solfrak[!(solfrak+a+b>1)]){ if (a+b+c<=1){ albukz=rbind(albukz, c(a,b,c,1-a-b-c))}} albukz=t(apply(buck+albukz,1,sort)) albukz=albukz[!duplicated(albukz),] if (is.matrix(albukz)){ bezt=max(apply(albukz,1,petimpty,hor=hor-1)) }else{ bezt=petimpty(albukz,hor-1)} return(bezt)} petimpty=function(buck,hor){ if (hor>1){ albukz=NULL for (i in 1:3) for (j in (i+1):4) albukz=rbind(albukz,c(buck[-c(i,j)],0,0)) albukz=t(apply(albukz,1,sort)) albukz=albukz[!duplicated(albukz),] if (is.matrix(albukz)){ bezt=min(apply(albukz,1,petifil,hor))}else{ bezt=petifil(albukz,hor)} }else{ bezt=sort(buck)[2]+1} return(bezt)}

which led to a most surprising outcome:

> petifil(hor=2) [1] 1.333 > petifil(hor=3) [1] 1.5 > petifil(hor=4) [1] 1.5 > petifil(hor=5) [1] 1.5

that is no feasible strategy to beat the value 1.5 liters. Which actually stands way below two liters, the maximum content of the bucket produced in the solution!

March 12, 2018 at 11:03 pm

You missed a word: Bob can only empty two *adjacent* buckets.

With your wording, I think the solution would be 5/3 (which you can’t reach because of your constraint on the portions allowed for Alice).

March 13, 2018 at 7:25 am

I almost invariably miss a word…!