Here you will find daily news and tutorials about R, contributed by over 750 bloggers.
There are many ways to follow us - By e-mail:On Facebook: If you are an R blogger yourself you are invited to add your own R content feed to this site (Non-English R bloggers should add themselves- here)

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…