Le Monde puzzle [#947]

February 1, 2016
By

(This article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers)

Another boardgame in Le Monde mathematical puzzle :

Given an 8×8 chequerboard,  consider placing 2×2 tiles over this chequerboard until (a) the entire surface is covered and (b) removing a single 2×2 tile exposes some of the original chequerboard. What is the maximal number of 2×2 tiles one can set according to this scheme? And for a 10×10 chequerboard?

This puzzle reminded me of Wilfrid Kendall’s introduction to perfect sampling  with leaves seen through a ceiling window falling from above, until sky was no longer visible. The representation was used by Wilfrid to explain that coupling from the past did not need to go all the way back to infinity:

Defining a random coverage of the chequerboard by those 2×2 tiles amounts to selecting a random permutation þ of 1:(n-1)² and finding the subvector of þ producing a full coverage

 grid=matrix(0,n,n)
 path=sample(1:(n-1)^2) #random permutation
 path=path+((path-1)%/%(n-1)) #account for border shift
 i=1
 neigh=c(0,1,n,n+1)
 while (min(grid)==0){ #all entries covered
   grid[path[i]+neigh]=grid[path[i]+neigh]+1
   i=i+1
 }
 i=i-1

Then removing superfluous tiles:

for (k in sample(1:i)){
 krid=grid
 krid[path[k]+neigh]=krid[path[k]+neigh]-1
 if (min(krid)>0){ #off used below
   off[k]=FALSE; grid=krid} #useless tile
 }

And checking the remaining ones are truly essential:

mingrid=0
for (k in (1:i)[off]){
 krid=grid
 krid[path[k]+neigh]=krid[path[k]+neigh]-1
 mingrid=max(mingrid,min(krid))
 }
sky=(mingrid>0) #rejection of the grid

leads to the maximum number of tiles to be [at least] M=16,25,37,54 for n=6,8,10,12…

Filed under: Books, Kids, pictures, R, Statistics Tagged: aperiodicity, chequerboard, coupling from the past, dead leaves, Le Monde, mathematical puzzle, R, Wilfrid Kendall

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 on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



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)