Le Monde puzzle [#947]

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

 path=sample(1:(n-1)^2) #random permutation
 path=path+((path-1)%/%(n-1)) #account for border shift
 while (min(grid)==0){ #all entries covered

Then removing superfluous tiles:

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

And checking the remaining ones are truly essential:

for (k in (1:i)[off]){
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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s