Le Monde puzzle [#14.2]

May 14, 2011
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

I received at last my weekend edition of Le Monde and hence the solution proposed by the authors (Cohen and Busser) to the puzzle #14. They obtain a strategy that only requires at most 19 steps. The idea is to start with a first test, which gives a reference score S0, and then work on groups of four questions, whose answers can be found in at most three steps. For instance, starting with x1,…,x25, the second test uses (1-x1),(1-x2),x3,…,x25, and changes the score S0 by -2,2 or 0. In the first two cases, this determines y1,y2 and it suffices to use x1,x2,(1-x3),(1-x4),x5…,x25, to find y3,y4 in one or two steps. If the score S0 does not change, considering x1,(1-x2),(1-x3),(1-x4),x5…,x25, and then maybe x1,(1-x2),x3,(1-x4),x5…,x25, produces again the value of y1,…,y4. If one repeats the algorithm one group of four after another, there are six such groups and the maximal number of step is

1+6*3=19

since the final answer y25 is known by deduction from S0. An additional improvement not mentioned in the journal is achieved in checking after any change whether or not the new score is equal to zero. (In both my solution and theirs, there is an extra step to propose the correct solution, which means in my case an exact average of steps equal to 25, by the geometric argument.)

For the current solution, here is an R code that evaluates the distribution of the number of steps:

rangep=rep(0,25)
for (t in 1:10^5){

s=2
for (j in 1:6){

y=sample(c(0,1),4,rep=T)
x=z=rep(1,4)
Delta0=sum(as.numeric(y!=x))

z[1:2]=0
Delta=sum(as.numeric(y!=z))

if (abs(Delta-Delta0)==2){
z=c(1,1,0,0)
Delta=sum(as.numeric(y!=z))
s=s+2+(abs(Delta-Delta0)!=2)

}else{
z=c(1,0,0,0)
Delta=sum(as.numeric(y!=z))
s=s+2+(abs(Delta-Delta0)!=3)
}
}
rangep[s]=rangep[s]+1
}

The fit by a binomial is rather poor, but this is not surprising given the two-stage decision. In any case, this does better than my earlier solution!

Filed under: Books, R, University life Tagged: Le Monde, mathematical puzzle

To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , ,

Comments are closed.

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)