Le Monde puzzle [#1014]


One of those Le Monde puzzles where a computational solution seems out of reach: given 2N batteries out of which N are charged, how many tests of pairs of batteries are necessary to find a working pair? I first tried a brute force recursive resolution checking all (2N-1)N orders of pairs over all (2N)! permutations of 0…01…1, but the magnitude of the exploration is such that the program failed to conclude for N=3! After realising that N+4 is an upper bound on the number of attempts (since testing all N disjoint pairs until success or exhaustion leaves 4 attempts to find the two operative batteries within a couple of tested pairs), I managed to cap the depth of the recursion into the following R code:

library(combinat)
N=4
permz=permn(rep(c(0,1),N))
seqz=matrix(0,factorial(2*N),2*N)
for (i in 1:factorial(2*N)) seqz[i,]=permz[[i]]

optest=function(earl,scorz,N){
#remaining pairs
best=N+4
if (length(earl)>N+3) return(best)
for (i in 1:(2*N-1))
for (j in ((i+1):(2*N))){
prez=i+2*N*j
if (!(prez%in%earl)){
scorzz=apply(cbind(scorz,seqz[,i]*seqz[,j]),1,max)
if (min(scorzz)==1){
best=length(earl)+1
break()}else{
best=min(best,optest(c(earl,prez),scorzz,N))}}
if (best==6) break()
}
return(best)}

optest(earl=c(1+2*N*2,1+2*N*3),
scorz=apply(matrix(as.vector(seqz[,c(1,1)])*
    as.vector(seqz[,c(2,3)]),ncol=2),1,max),N=N)

which returned a solution for N=3 (6 tests are enough, testing all combinations of the first three batteries then all combinations of the last three) but is still running for N=4! (I wonder at a possible resolution by modelling this puzzle though a very special type of multi-armed bandit problem with (pairwise) aggregated outcomes, but I did not go any further in that direction.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s