# Le Monde puzzle [#947]

**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**nother boardgame in Le Monde mathematical puzzle :

Given an 8×8 chequerboard, consider placing 2×2 tiles over thischequerboard 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?

**T**his 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

**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.