riddle by attrition

The weekend riddle from The Riddler is rather straightforward [my wording and simplification]:

Construct a decimal number X between 0 and 1 by drawing the first digit a¹ uniformly over {0,1,…,9}, the second digit a² uniformly over {0,1,…,9}, &tc., until 0 is attained. What is the expectation of this random variable X?

Since each new digit has expectation half of the previous digit, the expectation is an infinite geometric series with common ratio 20⁻¹ and factor 9, leading to an expectation of 9/19. As verified with the following R code:

skr<-function(){
  a=9;b=0
  while((a<-sample(rep(0:a,2),1))>0)b=10*b+a
  while(b>=1)b=b/10
  return(b)}

blue skies over Batignoles [jatp]

a bar for MCMC algorithms [jatp]

Le Monde puzzle (rainy Sunday!)

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 2ⁱ3^j. Considering 2ⁱ3^j.in box 1, say, and 2ⁱ⁺¹3^j, 2ⁱ3^j+1, and 2ⁱ⁺²3^j.in boxes 2, 3, and 4 respectively, 6×2ⁱ3^j=2ⁱ⁺¹3^j+1 cannot be in boxes 2 and 3. Furthermore, since 2ⁱ⁺²3^j=2×2ⁱ⁺¹3^j, is in box 4, 2ⁱ⁺¹3^j+1=3×2ⁱ⁺¹3^j cannot be in box 4 either. Ergo, it is in box 1.