Le Monde puzzle [#14]

May 13, 2011
By

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

Last 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.

Hence, if the correct answers are y1,…,y25, and the first guess is x1,…,x25, all taking values in {0,1}, the value of

(y_1-x_1)^2+\cdots+(y_{25}-x_{25})^2

is known. Changing only x25 into (1-x25) leads to the knowledge of the corresponding y25. If we keep changing each xi one at a time and downwards, in at most 24 steps, we know y25,…,y2, thus (y1-x1, hence y1. This shows that there exists a strategy with 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 to explore 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=sum((x[1:p]-y[1:p])^2) while ((Delta>0)&&(Delta

whose output is

> rangep[1]

1

so there was one occurrence where eliminating one yi at a time, we need to do the 25 steps. (Note I am not saying this is the optimal strategy, just one that satisfies the constraint.)

Filed under: R Tagged: Le Monde, mathematical puzzle, multiple answer test, R

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)