## Le Monde puzzle [#1014]

**O**ne 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