## Le Monde puzzle [#1087]

**A **board-like Le Monde mathematical puzzle in the digit category:

Given a (k,m) binary matrix, what is the maximum number S of entries with only one neighbour equal to one? Solve for k=m=2,…,13, and k=6,m=8.

For instance, for k=m=2, the matrix

is producing the maximal number 4. I first attempted a brute force random filling of these matrices with only a few steps of explorations and got the numbers 4,8,16,34,44,57,… for the first cases. Since I was convinced that the square k² of a number k previously exhibited to reach its maximum as S=k² was again perfect in this regard, I then tried another approach based on Gibbs sampling and annealing (what else?):

gibzit=function(k,m,A=1e2,N=1e2){ temp=1 #temperature board=sole=matrix(sample(c(0,1),(k+2)*(m+2),rep=TRUE),k+2,m+2) board[1,]=board[k+2,]=board[,1]=board[,m+2]=0 #boundaries maxol=counter(board,k,m) #how many one-neighbours? for (t in 1:A){#annealing for (r in 1:N){#basic gibbs steps for (i in 2:(k+1)) for (j in 2:(m+1)){ prop=board prop[i,j]=1-board[i,j] u=runif(1) if (log(u/(1-u))<temp*(counter(prop,k,m)-val)){ board=prop;val=counter(prop,k,m) if (val>maxol){ maxol=val;sole=board}} }} temp=temp*2} return(sole[-c(1,k+2),-c(1,m+2)])}

which leads systematically to the optimal solution, namely a perfect square k² when k is even and a perfect but one k²-1 when k is odd. When k=6, m=8, all entries can afford one neighbour exactly,

> gibzbbgiz(6,8) [1] 48 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [1,] 1 0 0 1 1 0 0 1 [2,] 1 0 0 0 0 0 0 1 [3,] 0 0 1 0 0 1 0 0 [4,] 0 0 1 0 0 1 0 0 [5,] 1 0 0 0 0 0 0 1 [6,] 1 0 0 1 1 0 0 1

but this does not seem feasible when k=6, m=7, which only achieves 40 entries with one single neighbour.

## Leave a Reply