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

\begin{matrix} 0 &0\\ 1 &1\\ \end{matrix}

\begin{matrix} 0 &0\\ 1 &1\\ \end{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))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.

To 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 on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more…



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook
Favorite

Leave a Comment