A griddy Le Monde mathematical puzzle:
- On a 4×5 regular grid, find how many nodes need to be turned on to see all 3×4 squares to have at least one active corner in case of one arbitrary node failing.
- Repeat for a 7×9 grid.
The question is open to simulated annealing, as in the following R code:
n=3;m=4;np=n+1;mp=m+1
cvr=function(grue){
grud=grue
obj=(max(grue)==0)
for (i in (1:length(grue))[grue==1]){
grud[i]=0
obj=max(obj,max((1-grud[-1,-1])*(1-grud[-np,-mp])*
(1-grud[-np,-1])*(1-grud[-1,-mp])))
grud[i]=1}
obj=99*obj+sum(grue)
return(obj)}
dumban=function(grid,T=1e3,temp=1,beta=.99){
obj=bez=cvr(grid)
sprk=grid
for (t in 1:T){
grue=grid
if (max(grue)==1){ grue[sample(rep((1:length(grid))[grid==1],2),1)]=0
}else{ grue[sample(1:(np*mp),np+mp)]=1}
jbo=cvr(grue)
if (bez>jbo){ bez=jbo;sprk=grue}
if (log(runif(1))<(obj-jbo)/temp){
grid=grue;obj=cvr(grid)}
temp=temp*beta
}
return(list(top=bez,sol=sprk))}
leading to
> dumban(grid,T=1e6,temp=100,beta=.9999)
$top
[1] 8
$sol
[,1] [,2] [,3] [,4] [,5]
[1,] 0 1 0 1 0
[2,] 0 1 0 1 0
[3,] 0 1 0 1 0
[4,] 0 1 0 1 0
which sounds like a potential winner.
