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.)

10 Responses to “Le Monde puzzle [#755?]”

  1. 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
    }
    
    
    	
    	
  2. Chris Jackson Says:

    Why did you sort when adding the columns and rows? Great post!

    • 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…

  3. 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

    :)

  4. in fact I forgot about the tunning temperature t because the first time I hit the button it found the solution…

    • I adapted your code to the product case and it is still running… Finding matrices with equal products seems much harder!!!

    • 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!

  5. 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)

    • 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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 706 other followers