Le Monde puzzle (rainy Sunday!)

October 20, 2012
By

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

On October 14, the weekend edition of Le Monde had the following puzzle: consider four boxes that contain all integers between 1 and 9999, in such a way that for any N, N, 2N, 3N, and 4N are in four different boxes. If 1,2,3 and 4 are in boxes labelled 1,2,3 and 4, respectively, in which box is 972 located? The direct resolution of the puzzle is that, since N and 6N are always in the same box (proof below), 972=2²x3⁵ is the same box as 162 and 27. Filling the boxes by considering the multiples of 2,…,9 leads to 27 being in the second box. Here is however a brute force resolution in R, filling the boxes by looking at the three multiples of each value met so far.

boxin=function(N){ #gives the box N is in

 sum(N==box1)+2*sum(N==box2)+3*sum(N==box3)+4*sum(N==box4)
 }

nomul=function(N,j){ #check for no multiple in the same box

 if (j==1) nopb=((sum(N==2*box1)+sum(N==3*box1)+sum(N==4*box1))==0)&&
                ((sum(2*N==box1)+sum(3*N==box1)+sum(4*N==box1))==0)
 if (j==2) nopb=((sum(N==2*box2)+sum(N==3*box2)+sum(N==4*box2))==0)&&
                ((sum(2*N==box2)+sum(3*N==box2)+sum(4*N==box2))==0)
 if (j==3) nopb=((sum(N==2*box3)+sum(N==3*box3)+sum(N==4*box3))==0)&&
                ((sum(2*N==box3)+sum(3*N==box3)+sum(4*N==box3))==0)
 if (j==4) nopb=((sum(N==2*box4)+sum(N==3*box4)+sum(N==4*box4))==0)&&
                ((sum(2*N==box4)+sum(3*N==box4)+sum(4*N==box4))==0)
 nopb
 }

box1=c(1)
box2=c(2)
box3=c(3)
box4=c(4)
N=1

while (N<972){

  allbox=c(box1,box2,box3,box4)
  N=min(allbox[allbox>N])
  ndx=rep(0,4)
  ndx[1]=boxin(N)
  for (t in 2:4){

    if (sum(t*N==allbox)>0){
      ndx[t]=boxin(t*N)}
    }
  if (sum(ndx==0)==1){ #no choice
    ndx[ndx==0]=(1:4)[-ndx[ndx>0]]
  }else{
    while (min(ndx)==0){

     pro=ndx
     pro[ndx==0]=sample((1:4)[-ndx[ndx>0]])
     okk=nomul(N,pro[1])&&nomul(2*N,pro[2])&&nnomul(3*N,pro[3])&&nomul(4*N,pro[4])
     if (okk) ndx=pro
     }
  }
  for (t in 2:4){

   if (ndx[t]==1) box1=unique(c(box1,t*N))
   if (ndx[t]==2) box2=unique(c(box2,t*N))
   if (ndx[t]==3) box3=unique(c(box3,t*N))
   if (ndx[t]==4) box4=unique(c(box4,t*N))
   }
  }
boxin(972)

To prove that N and 6N are in the same box, consider that the numbers whose box is set are of the form 2i3j. Considering 2i3j.in box 1, say, and 2i+13j, 2i3j+1, and 2i+23j.in boxes 2, 3, and 4 respectively, 6×2i3j=2i+13j+1 cannot be in boxes 2 and 3. Furthermore, since 2i+23j=2×2i+13j, is in box 4, 2i+13j+1=3×2i+13j cannot be in box 4 either. Ergo, it is in box 1.


Filed under: Kids, R Tagged: Le Monde, mathematical puzzle, weekend

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

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: 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.