Le Monde puzzle [#920]

[This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

A puzzling Le Monde mathematical puzzle (or blame the heat wave):

A pocket calculator with ten keys (0,1,…,9) starts with a random digit n between 0 and 9. A number on the screen can then be modified into another number by two rules:
1. pressing k changes the k-th digit v whenever it exists into (v+1)(v+2) where addition is modulo 10;
2. pressing 0k deletes the (k-1)th and (k+1)th digits if they both exist and are identical (otherwise nothing happens.
Which 9-digit numbers can always be produced whatever the initial digit?

I did not find an easy entry to this puzzle, in particular because it did not state what to do once 9 digits had been reached: would the extra digits disappear? But then, those to the left or to the right? The description also fails to explain how to handle n=000 000 004 versus n=4.

Instead, I tried to look at the numbers with less than 7 digits that could appear, using some extra rules of my own like preventing numbers with more than 9 digits. Rules which resulted in a sure stopping rule when applying both rules above at random:

leplein=rep(0,1e6)
for (v in 1:1e6){
 x=as.vector(sample(1:9,1))
 for (t in 1:1e5){
  k=length(x) #as sequence of digits
  if (k<3){

   i=sample(rep(1:k,2),1)
   x[i]=(x[i]+1)%%10
   y=c(x[1:i],(x[i]+1)%%10)
   if (i<k){ x=c(y,x[(i+1):k])}else{ x=y}
 }else{

  prop1=prop2=NULL
  difs=(2:(k-1))[abs(x[-(1:2)]-x[-((k-1):k)])==0]
  if (length(difs)>0) prop1=sample(rep(difs,2),1)
  if (k<9) prop2=sample(rep(1:k,2),1)

  if (length(c(prop1,prop2))>1){
   if (runif(1)<.5){

    x[prop2]=(x[prop2]+1)%%10
    y=c(x[1:prop2],(x[prop2]+1)%%10)
    if (prop2<k){ x=c(y,x[(prop2+1):k])}else{ x=y}
    }else{
      x=x[-c(prop1-1,prop1+1)]}
    while ((length(x)>1)&(x[1]==0)) x=x[-1]}

  if (length(c(prop1,prop2))==1){
    if (is.null(prop2)){ x=x[-c(prop1-1,prop1+1)]
    }else{
     x[prop2]=(x[prop2]+1)%%10
     y=c(x[1:prop2],(x[prop2]+1)%%10)
     if (prop2<k){ x=c(y,x[(prop2+1):k])
     }else{ x=y}
     x=c(x[1:(prop2-1)],
       (x[prop2]+1)%%10,
       (x[prop2]+2)%%10,x[(prop2+1):k])}
    while ((length(x)>1)&(x[1]==0)) x=x[-1]}

  if (length(c(prop1,prop2))==0) break()
  }

 k=length(x)
 if (k<7) leplein[sum(x*10^((k-1):0))]=
          leplein[sum(x*10^((k-1):0))]+1
}}

code that fills an occupancy table for the numbers less than a million over 10⁶ iterations. The solution as shown below (with the number of zero entries over each column) is rather surprising in that it shows an occupancy that is quite regular over a grid. While it does not answer the original question…

lemonde920


Filed under: Books, Kids, R, Statistics, University life Tagged: Le Monde, mathematical puzzle

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

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)