# Le Monde puzzle (rainy Sunday!)

October 20, 2012
By

(This article was originally published at Xi'an's Og » R, and syndicated at StatsBlogs.)

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&lt;972){

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

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

pro=ndx
pro[ndx==0]=sample((1:4)[-ndx[ndx&gt;0]])
okk=nomul(N,pro[1])&amp;&amp;nomul(2*N,pro[2])&amp;&amp;nnomul(3*N,pro[3])&amp;&amp;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

Please comment on the article here: Xi'an's Og » R

Tags: , , , ,

 Tweet

Email: