## Le Monde puzzle [#14]

**L**ast week Le Monde puzzle *(I have not received this week issue yet!)* was about deriving an optimal strategy *in less than 25 steps* for finding the 25 answers to a binary multiple choice test, when at each trial, only the number of correct answers is known.

**H**ence, if the correct answers are *y _{1},…,y_{25}*, and the first guess is

*x*, all taking values in {0,1}, the value of

_{1},…,x_{25}is available. Changing only *x _{25}* into

*(1-x*leads to the knowledge of the corresponding

_{25})*y*. This takes two steps. However, if we keep changing each

_{25}*x*one at a time and downwards, in

_{i}*at most*24 steps, we know

*y*, thus

_{25},…,y_{2}*(y*, hence

_{1}-x_{1})²*y*. Indeed, we know the remaining

_{1}*y*‘s as soon as as the sum is either zero or the number of terms. This shows that there exists a strategy with

_{i}*25 steps or less*that provides the answer to the multiple choice test. If we are unlucky enough in our choice, can we reach the 25 steps? Here is a simulation experiment in R that explores this question, where the stopping rule is associated with all wrong or all right remaining answers.

rangep=rep(0,25) for (t in 1:10^6){ y=sample(c(0,1),25,rep=T) x=sample(c(0,1),25,rep=T) p=25 Delta=cumsum((x-y)^2) while ((Delta[p]>0)&&(Delta[p]<p)){ p=p-1} rangep[p]=rangep[p]+1 }

whose output is

> rangep[1]/10^6 [1] 0.500851 > sum((25:1)*rangep)/10^6 [1] 24.00053

and the mode of the distribution of the p’s seems to be at 1, which means that in 50% of the cases, when eliminating/finding one *y _{i}* at a time, we need to do the 25 steps. The average number of steps is furthermore 24. Mathematically, the distribution of the number of steps relates to the longest sequence with the same value in a Bernouilli experiment, which is a Geometric(1/2) truncated at 24.

*(Note that an earlier version with a basic R mistake wrongly concluded to a binomial fit! Also, I am not saying this is the optimal strategy, just one that satisfies the constraint.)*

## Leave a Reply