Le Monde puzzle [#1076]

December 26, 2018
By

[This article was first published on R – Xi'an's Og, 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 cheezy Le Monde mathematical puzzle : (which took me much longer to find [in the sense of locating] than to solve, as Warwick U does not get a daily delivery of the newspaper [and this is pre-Brexit!]):

Take a round pizza (or a wheel of Gruyère) cut into seven identical slices and turn one slice upside down. If the only possibly moves are to turn three connected slices to their reverse side, how many moves at least are needed to recover the original configuration? What is the starting configuration that requires the largest number of moves?

Since there are ony N=2⁷ possible configurations, a brute force exploration is achievable, starting from the perfect configuration requiring zero move and adding all configurations found by one additional move at a time… Until all configurations have been visited and all associated numbers of steps are stable. Here is my R implementation

nztr=lengz=rep(-1,N) #length & ancestor
nztr[0+1]=lengz[0+1]=0 
fundz=matrix(0,Z,Z) #Z=7
for (i in 1:Z){ #only possible moves
  fundz[i,c(i,(i+1)%%Z+Z*(i==(Z-1)),(i+2)%%Z+Z*(i==(Z-2)))]=1
  lengz[bit2int(fundz[i,])+1]=1
  nztr[bit2int(fundz[i,])+1]=0}
while (min(lengz)==-1){ #second loop omitted
  for (j in (1:N)[lengz>-1])
  for (k in 1:Z){
    m=bit2int((int2bit(j-1)+fundz[k,])%%2)+1
    if ((lengz[m]==-1)|(lengz[m]>lengz[j]+1)){
      lengz[m]=lengz[j]+1;nztr[m]=j}
      }}

Which produces a path of length five returning (1,0,0,0,0,0,0) to the original state:

> nztry(2)
[1] 1 0 0 0 0 0 0
[1] 0 1 1 0 0 0 0
[1] 0 1 0 1 1 0 0
[1] 0 1 0 0 0 1 0
[1] 1 1 0 0 0 0 1
[1] 0 0 0 0 0 0 0

and a path of length seven in the worst case:

> nztry(2^7)
[1] 1 1 1 1 1 1 1
[1] 1 1 1 1 0 0 0
[1] 1 0 0 0 0 0 0
[1] 0 1 1 0 0 0 0
[1] 0 1 0 1 1 0 0
[1] 0 1 0 0 0 1 0
[1] 1 1 0 0 0 0 1
[1] 0 0 0 0 0 0 0

Since the R code was written for an arbitrary number Z of slices, I checked that there is no solution for Z being a multiple of 3.

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

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.



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers

Sponsors

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)