Grid Max and Min

[davar55]

Let the measure of a grid of numbers be the sum, over all rows and
columns, of the product of the elements in that row or column.

Find 5x5 grids containing the integers 1 to 25 that (a) maximize, and
(b) minimize this measure.

[S485122]

I tried my solution on a 3X3 grid only, I think it will expand to any grid.

To maximise fill the grid in order (for the 3X3 grid it would give the following :
1 2 3
4 5 6
7 8 9
the sum of products will be 1*2*3+4*5*6+7*8*9+1*4*7+2*5*8+3*6*9=900)

To minimize but the biggest numbers in a diagonal, then fill the "diagonal below with the smallest numbers wrapping when necessary... (for the 3x3 grid :
9 4 3
1 8 5
6 2 7
the sum of products will be 9*4*3+1*8*5+6*2*7+9*1*6+4*8*2+3*5*7=455)

Hope I was not to quick to respond overlooking some subtility.

Jacob

[Brian-E]

Originally Posted by S485122

I tried my solution on a 3X3 grid only, I think it will expand to any grid.

To maximise fill the grid in order (for the 3X3 grid it would give the following :
1 2 3
4 5 6
7 8 9
the sum of products will be 1*2*3+4*5*6+7*8*9+1*4*7+2*5*8+3*6*9=900)

To minimize but the biggest numbers in a diagonal, then fill the "diagonal below with the smallest numbers wrapping when necessary... (for the 3x3 grid :
9 4 3
1 8 5
6 2 7
the sum of products will be 9*4*3+1*8*5+6*2*7+9*1*6+4*8*2+3*5*7=455)

Hope I was not to quick to respond overlooking some subtility.

Jacob

By brute force search I found some slightly better solutions for the 3x3 grid:



Maximum:

7 9 8
1 5 3
2 6 4
(sum of products = 947)

Minimum:

8 1 7
2 9 4
5 6 3
(sum of products = 436)

[Brian-E]

Here are the best results I can find for the 5 x 5 grid, but I am sure they can be improved:




Maximum:
3 20 5 9 1
13 22 19 15 12
17 25 24 14 18
11 23 16 7 6
8 21 10 4 2
Measure: 9526332

Minimum:
8 13 20 10 6
5 17 22 12 3
24 9 18 1 25
7 4 14 21 19
16 15 2 23 11
Measure: 1167798

[S485122]

Indeed I was to quick.
I will work by rows, of course the same result could be obtained by columns and after having a grid the results doe snot change swapping rows around or swapping columns around.

For the maximum grid I just fill a first row with the highest numbers to get the maximum product. My mistake was not to use the highest numbers left to fill the column under the highest number in the first row and going on like that. That gives (filling the numbers with 0's for better reading since the code tag does not work inside the spoilertag) :
25 24 23 22 21
20 16 12 08 04
19 15 11 07 03
18 14 10 06 02
17 13 09 05 01
for a total of 10 870 524

For the minimum I did not find an easy fill method. I fiddled the numbers around to get each product to minimise to (25!)^0,2 or about 109 176. The best I could get :
25 17 13 21 01
24 15 08 02 18
05 06 07 22 23
11 04 16 12 14
03 19 10 09 20
for a total of 1 094 309. That probably is not a best result, but it is not to far from the theoretical best of 1 091 765 one gets if all products are equal.
Jacob

[henryzz]

i take it it is impossible to brute force check 5x5

[retina]

Originally Posted by henryzz

i take it it is impossible to brute force check 5x5

My brief and maybe inaccurate calculation gives ~67322960257512960000 (6.7e19) combinations.

25!/(5!*5!*4*4)?

So not impossible, but perhaps not practical in any reasonable time frame? Depends on the algorithm efficiency and how much raw CPU power you want to throw at it.

[davieddy]

Originally Posted by retina

25!/(5!*5!*4*4)?

Assuming 4*4 refers to rotations and reflections, I think
it should be replaced by 2 (one 90 degree rotation or reflection in a diagonal)
since the rest can be accomplished by swapping rows and/or columns.

[davieddy]

And the number of distinct rotations/reflections of the
grid is not 16 but 8.
David

[m_f_h]

I remember a programming contest where this had to be done.
These solutions carry somebody's name ... I'll try to find it again via google ...

(not yet found) some precisions from memory: in that contest, the matrices were quite big
(20x20, etc) and one had not necessarily to find the best solution ; for any solution (list of matrix entries) submitted one got a score calculated as function of the difference w.r.t. the previous best solution
(I think scores were awarded both for minimal and maximal sums of products ; maybe diagonals were included (or not ?))

[davieddy]

Originally Posted by m_f_h

I remember a programming contest where this had to be done.
These solutions carry somebody's name name... I'll try to find it again via google ...

This sort of thing always has to be done.
There's nothing worse than finding your program has trawled
through 5!*5! more arrangements than necessary