## Le Monde puzzle [#882] A terrific Le Monde mathematical puzzle:

All integers between 1 and n² are written in an (n,n)  matrix under the constraint that two consecutive integers are adjacent (i.e. 15 and 13 are two of the four neighbours of 14). What is the maximal value for the sum of the diagonal of this matrix?

Indeed, when considering a simulation resolution (for small values of m), it constitutes an example of self-avoiding random walk: when inserting the integers one by one at random, one produces a random walk over the (n,n) grid.

While the solution is trying to stick as much as possible to the diagonal vicinity for the descending sequence n²,n²-1, &tc., leaving space away from the diagonal for the terminal values, as in this example for n=5,

```25 22 21 14 13
24 23 20 15 12
01 02 19 16 11
04 03 18 17 10
05 06 07 08 09
```

simulating such a random walk is a bit challenging as the brute force solution does not work extremely well:

```n=5
n2=n^2

init=function(){
board=invoard=matrix(0,n,n)
set=rep(0,n2)

start=val=n2 #sample(1:n2,1)
neigh=board[start]=val
invoard[val]=start
set[val]=1

return(list(board=board,invoard=invoard,
set=set,neigh=neigh))
}

voisi=function(i){
a=arrayInd(i,c(n,n))
b=a;a=a

if ((a>1)&(a<n)){
voizin=(a+c(-1,1))+(b-1)*n}else{
if (a==1) voizin=a+1+(b-1)*n
if (a==n) voizin=a-1+(b-1)*n}

if ((b>1)&(b<=n)){
voizin=c(voizin,a+(b+c(-2,0))*n)}else{
if (b==1) voizin=c(voizin,a+b*n)
if (b>n) voizin=c(voizin,a+(b-2)*n)}

voizin=voizin[(voizin>0)&(voizin<=n2)]
return(voizin)
}

a=init()
board=a\$board
invoard=a\$invoard
set=a\$set
neigh=a\$neigh

while (sum(set)<n2){

if (length(neigh)==1) neighb=neigh+c(-1,1)
if (length(neigh)==2) neighb=c(min(neigh)-1,
max(neigh)+1)
neighb=neighb[(neighb>0)&(neighb<=n2)]
neighb=neighb[set[neighb]==0]

for (i in 1:length(neighb)){

j=1
if (i==2) j=1+(length(neigh)>1)
loc=voisi(invoard[neigh[j]])
loc=loc[board[loc]==0]

if (length(loc)==0) break() #no solution
if (length(loc)==1){
board[loc]=neighb[i]
invoard[neighb[i]]=loc
set[neighb[i]]=1}
if (length(loc)>1){ #2 or more solutions
val=sample(loc,1)
board[val]=neighb[i]
invoard[neighb[i]]=val
set[neighb[i]]=1}
}

if (min(set[neighb])==0){#start afresco
a=init()
board=a\$board
invoard=a\$invoard
set=a\$set
neigh=a\$neigh
}else{
if (length(neighb)==1) neigh=neighb
if (length(neighb)>1){
neigh=sort(neighb)
neigh=neigh[(neigh>0)&(neigh<=n2)]
}}
}
```

the reason being that the chain often has to restart a fresco, the more the larger n is… For n=5, I still recovered the optimal solution:

```> while (sum(diag(board))<93)
+ source("lemonde882.R")
[,1] [,2] [,3] [,4] [,5]
[1,]    9    8    7    6    1
[2,]   10   17   18    5    2
[3,]   11   16   19    4    3
[4,]   12   15   20   23   24
[5,]   13   14   21   22   25
```

but running the R code for n=7 towards finding the maximum (259?) takes quite a while and 50 proposals for n=8 took the whole night… If I run a simple log-log regression on the values obtained for n=2,…,7, the prediction for n=10 is 768. A non-stochastic prediction is 870.

As a last ditch attempt to recover the sequence n²-2k along the diagonal for k=0,1,…, I modified my code to favour simulations close to the diagonal at the start, as

```if (length(loc)>1){#two or more solutions
val=sample(loc,1,
proba=exp(-abs(loc%%n-1-loc%/%n)/sum(set)))
```

which produces higher diagonal values but also more rejections.

### 3 Responses to “Le Monde puzzle [#882]”

1. Jean-Louis Foulley Says:

Thanks Christian for commenting in detail on this brain-teasing grid problem.
The solution given by Busser and Cohen in Le Monde for n=10 allows as you mentioned it to derive a general analytical solution for n even. The case n odd is still pending. Did you find sth?
This game is a good opportunity to celebrate the birth centennial of Martin Gardner (21 oct 1914, 22 may 2010) who inspired so many people in his Mathematical Games column of Scientific American. See a brief recollection of his main topical columns on polyominoes, Penrose tiles, game of lifes, RSA cryptography, etc… in the last issue of SA by S Mulcahy and D Richards.

2. natesh Says:

hmm, interesting, but the optimal solution does not contain
all the n^-2k, numbers right?

• xi'an Says:

The optimal solution is a (n,n) grid containing all integers 1,2,..,n², with n²,n²-2,…,n²-2(n-2),[n²-2(n-2)]/2 along the diagonal when n is even.

This site uses Akismet to reduce spam. Learn how your comment data is processed.