## Le Monde puzzle (rainy Sunday!)

**O**n 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)

**T**o prove that N and 6N are in the same box, consider that the numbers whose box is set are of the form 2^{i}3^{j}. Considering 2^{i}3^{j}.in box 1, say, and 2^{i+1}3^{j}, 2^{i}3^{j+1}, and 2^{i+2}3^{j}.in boxes 2, 3, and 4 respectively, 6×2^{i}3^{j}=2^{i+1}3^{j+1} cannot be in boxes 2 and 3. Furthermore, since 2^{i+2}3^{j}=2×2^{i+1}3^{j}, is in box 4, 2^{i+1}3^{j+1}=3×2^{i+1}3^{j} cannot be in box 4 either. Ergo, it is in box 1.

October 21, 2012 at 2:33 pm

Reading the solution in Le Monde today, numbers others than the powers of 2 and 3 can be arbitrarily allocated to one box, with the same reasoning for their multiples by powers of 2 and 3.

There was also a subsidiary question about a similar scheme for nine boxes and a prohibition to see any pair out of N, 2N, …, 9N, within the same box but I find the resolution published in the next weekend edition rather unclear…