Le Monde puzzle [#755?]
Le Monde puzzle of last weekend was about sudoku-like matrices.
Consider an (n,n) matrix containing the integers from 1 to n². The matrix is “friendly” if the set of the sums of the rows is equal to the set of the sum of the columns. Find examples for n=4,5,6. Why is there no friendly matrix when n=9?
Checking for small n’s seems easy enough:
friend=function(n){
s=1
while (s>0){
A=matrix(sample(1:n^2),ncol=n)
s=sum(abs(sort(apply(A,1,sum))-
sort(apply(A,2,sum))))}
A
}
For instance, running
> friend(3)
[,1] [,2] [,3]
[1,] 8 4 2
[2,] 1 9 5
[3,] 6 3 7
> friend(4)
[,1] [,2] [,3] [,4]
[1,] 14 10 11 6
[2,] 13 3 12 8
[3,] 4 5 16 15
[4,] 9 1 2 7
> friend(5)
[,1] [,2] [,3] [,4] [,5]
[1,] 17 14 10 16 5
[2,] 8 19 7 15 22
[3,] 2 3 25 13 6
[4,] 11 12 18 1 21
[5,] 24 23 20 4 9
>friend(6)
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 14 4 36 30 10 18
[2,] 7 16 24 27 32 11
[3,] 21 25 12 5 22 17
[4,] 26 20 6 31 19 34
[5,] 3 35 1 28 9 29
[6,] 23 2 33 15 13 8
produces right answers. But the case n=6 proved itself almost too hard for brute-force handling!!! I have no time to devise a simulated-annealing code to speed up the resolution so this will have to wait till the next weekend edition of Le Monde. As to why n=9 does not enjoy a solution… (When n=2 there is no solution, as proven by the brute force exhibition of all cases.)
Xi'an's Og 
January 30, 2012 at 12:18 pm
The following function appears to provide quite a bit of speedup to the brute force case:
friend3 <- function(n) { set.seed(1) ss <- FALSE while (!ss) { A <- matrix(sample(1 : n^2), ncol = n) ss <- setequal(colSums(A), rowSums(A)) } A }January 30, 2012 at 12:33 pm
Thanks! Another R function I did not know…
January 28, 2012 at 11:20 pm
Why did you sort when adding the columns and rows? Great post!
January 29, 2012 at 8:12 am
Thanks! I used sort because the way the column was written I though the order of the sums did not matter, only the collection of those sums. If you remove the sort in s, the order of appearance of the sums matters and you are looking for a matrix where the sum of the first column equals the sum of the first row, the sum of the second column equals the sum of the second row, and so on…
January 28, 2012 at 3:23 pm
sss = function(A){
sum(abs(sort(apply(A,1,sum))-sort(apply(A,2,sum))))
}
friendmc = function(n,temp=3*log(n)){
A = matrix(sample(1:n^2),ncol=n)
s = sss(A)
while (s>0){
c1 = sample(1:n,1)
c2 = sample(1:n,1)
r1 = sample(1:n,1)
r2 = sample(1:n,1)
Aprop = A
Aprop[r1,c1] = A[r2,c2]
Aprop[r2,c2] = A[r1,c1]
sA = sss(A)
sAprop = sss(Aprop)
if (runif(1) < exp(temp*(-sAprop+sA))) A = Aprop
s = sss(A)
}
A
}
just found a friendly one for n=30
:)
January 28, 2012 at 12:53 pm
in fact I forgot about the tunning temperature t because the first time I hit the button it found the solution…
January 29, 2012 at 9:50 am
I adapted your code to the product case and it is still running… Finding matrices with equal products seems much harder!!!
January 29, 2012 at 2:37 pm
The metric chosen for our code is probably good for summation but not so great for factorisation. Something based on a differences in prime factorisation should be probably used. Good fun anyway, thanks of the post!
January 28, 2012 at 12:48 pm
Le Monde is wrong this time:
(brute force MCMC)
sss = function(A){
sum(abs(sort(apply(A,1,sum))-sort(apply(A,2,sum))))
}
friendmc = function(n,t=0.1){
A = matrix(sample(1:n^2),ncol=n)
s = sss(A)
while (s>0){
c1 = sample(1:n,1)
c2 = sample(1:n,1)
r1 = sample(1:n,1)
r2 = sample(1:n,1)
Aprop = A
Aprop[r1,c1] = A[r2,c2]
Aprop[r2,c2] = A[r1,c1]
sA = sss(A)
sAprop = sss(Aprop)
if (runif(1) < exp(-sAprop+sA)) A = Aprop
s = sss(A)
}
A
}
A9 = friendmc(9)
January 28, 2012 at 5:18 pm
Thanks for the MCMC solution, Krzysztoff! Actually, the wording of the problem was unclear. (And I confused sum and product in addition!) In the solutions found in today’s edition, the raw collection of the sums must be the same for rows and columns, not the ordered collection. The argument for preventing 9 to have a solution (in this restricted sense!) is that there are 10 prime numbers between 1 and 81 w/o any multiple, meaning that two must be in either one column or one row, a product that cannot be recovered…