Processing math: 0%
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 4 years ago

Max Alekseyev gravatar image

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first fixing at which squares we get values {1,2,,25} (we pick them in \binom{30}{25}=142506 ways), and then solving an Integer Linear Program. Here we denote elements of the matrix as a_{i,j}, and let S_i be the sums of elements of the i-th square (i=1,\dots,25). Then we introduce binary indicators p_{i,j} (i,j=1,\dots,25) telling whether S_i = j and constrainsts: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^25 p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} \geq 1\qquad\text{for }j=1,2,\dots,25. The solution above was solved on 1617-th selection of squares, within a few minutes.

click to hide/show revision 2
No.2 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first fixing selecting at which 25 squares we get values \{1,2,\dots,25\} (we pick them in \binom{30}{25}=142506 ways), and then solving an Integer Linear Program. Here In our ILP, we denote elements of the introduce integer variables a_{i,j} denoting matrix as a_{i,j}, elements, and let S_i be the sums of elements of the i-th square (i=1,\dots,25). Then we introduce binary indicators indicator variables p_{i,j} (i,j=1,\dots,25) telling whether $S_i = j$ j$, and constrainsts: constraints: $$\begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^25 \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} \geq 1\qquad\text{for }j=1,2,\dots,25.$$ The solution above was solved obtained on 1617-th selection of squares, within just a few minutes.minutes of running my Sage code.

click to hide/show revision 3
No.3 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which 25 squares we get values \{1,2,\dots,25\} (we pick them in there are \binom{30}{25}=142506 ways), ways to select such 25 squares), and then solving an Integer Linear Program. Programming problem.

In our ILP, we introduce integer variables a_{i,j} denoting the matrix elements, and let S_i be the sums of those elements of in the i-th selected square (i=1,\dots,25). Then Also, we introduce have binary indicator variables p_{i,j} (i,j=1,\dots,25) telling whether S_i = j, and constraints: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} \geq 1\qquad\text{for }j=1,2,\dots,25. The solution above was obtained on 1617-th selection of squares, within just a few minutes of running my Sage code.

click to hide/show revision 4
No.4 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which 25 squares we get values \{1,2,\dots,25\} there are \binom{30}{25}=142506 ways to select such 25 squares), and then solving an Integer Linear Programming problem.

In our ILP, we introduce integer variables a_{i,j} denoting the matrix elements, and let S_i be the sums of those elements in the i-th selected square (i=1,\dots,25). Also, Essentially we have want (S_1,S_2,\dots,S_{25}) be a permutation of \{1,2,\dots,25\}. For this purpose, we introduce binary indicator variables p_{i,j} (i,j=1,\dots,25) telling whether S_i = j, and constraints: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} \geq 1\qquad\text{for }j=1,2,\dots,25. The solution above was obtained on the 1617-th selection of squares, within just a few minutes of running my Sage code.

click to hide/show revision 5
No.5 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which 25 squares we get values \{1,2,\dots,25\} there (there are \binom{30}{25}=142506 ways to select make such 25 squares), a selection), and then by solving an Integer Linear Programming problem.

In our ILP, we introduce integer variables a_{i,j} denoting the matrix elements, and let S_i be the sums of those elements in the i-th selected square (i=1,\dots,25). Essentially we want (S_1,S_2,\dots,S_{25}) be a permutation of \{1,2,\dots,25\}. For this purpose, we introduce binary indicator variables p_{i,j} (i,j=1,\dots,25) telling whether S_i = j, and constraints: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} \geq 1\qquad\text{for }j=1,2,\dots,25. The solution above was obtained on the 1617-th selection of squares, within just a few minutes of running my Sage code.

click to hide/show revision 6
No.6 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which 25 squares we get values \{1,2,\dots,25\} (there are \binom{30}{25}=142506 ways to make such a selection), and then by solving an Integer Linear Programming problem.

In our ILP, we introduce integer variables a_{i,j} a_{u,v} (u,v=1,2,3,4) denoting the matrix elements, and let S_i be the sums of those elements in the i-th selected square (i=1,\dots,25). Essentially we want (S_1,S_2,\dots,S_{25}) be a permutation of \{1,2,\dots,25\}. For this purpose, we introduce binary indicator variables p_{i,j} (i,j=1,\dots,25) telling whether S_i = j, and constraints: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} \geq 1\qquad\text{for }j=1,2,\dots,25. The solution above was obtained on the 1617-th selection of squares, within just a few minutes of running my Sage code.

click to hide/show revision 7
No.7 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which 25 squares we get values \{1,2,\dots,25\} (there are \binom{30}{25}=142506 ways to make such a selection), and then by solving an Integer Linear Programming problem.

In our ILP, we introduce integer variables a_{u,v} (u,v=1,2,3,4) denoting the matrix elements, and let S_i be the sums of those elements in the i-th selected square (i=1,\dots,25). Essentially we want (S_1,S_2,\dots,S_{25}) be a permutation of \{1,2,\dots,25\}. For this purpose, we introduce binary indicator variables p_{i,j} (i,j=1,\dots,25) telling whether S_i = j, and constraints: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} \geq 1\qquad\text{for }j=1,2,\dots,25. The solution above was obtained on the 1617-th selection of squares, within just a few minutes of running my Sage code.

PS. Another solution:

9 3 6 5 
8 1 4 10 
11 2 16 -23 
19 -15 12 13
click to hide/show revision 8
No.8 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which 25 squares we get values \{1,2,\dots,25\} (there are \binom{30}{25}=142506 ways to make such a selection), and then by solving an Integer Linear Programming problem.

In our ILP, we introduce integer variables a_{u,v} (u,v=1,2,3,4) denoting the matrix elements, and let S_i be the sums of those elements in the i-th selected square (i=1,\dots,25). Essentially we want (S_1,S_2,\dots,S_{25}) be a permutation of \{1,2,\dots,25\}. For this purpose, we introduce binary indicator variables p_{i,j} (i,j=1,\dots,25) telling whether S_i = j, and constraints: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and $$\sum_{i=1}^{25} p_{i,j} \geq = 1\qquad\text{for }j=1,2,\dots,25.$$ The solution above was obtained on the $1617$-th selection of squares, within just a few minutes of running my Sage code.

PS. Another solution:

9 3 6 5 
8 1 4 10 
11 2 16 -23 
19 -15 12 13
click to hide/show revision 9
No.9 Revision

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which 25 squares we get values \{1,2,\dots,25\} (there are \binom{30}{25}=142506 ways to make such a selection), and then by solving an Integer Linear Programming problem.

In our ILP, we introduce integer variables a_{u,v} (u,v=1,2,3,4) denoting the matrix elements, and let S_i be the sums of those elements in the i-th selected square (i=1,\dots,25). Essentially we want (S_1,S_2,\dots,S_{25}) be a permutation of \{1,2,\dots,25\}. For this purpose, we introduce binary indicator variables p_{i,j} (i,j=1,\dots,25) telling whether S_i = j, and constraints: \begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25 and \sum_{i=1}^{25} p_{i,j} = 1\qquad\text{for }j=1,2,\dots,25. The solution above was obtained on the 1617-th selection of squares, within just a few minutes of running my Sage code.

PS. Another solution:

9 3 6 5 
8 1 4 10 
11 2 16 -23 
19 -15 12 13

PS2. There even exists a matrix delivering sums \{0,1,2,\dots,25\}, for example:

0 6 21 4 
9 7 -24 17 
14 -25 11 8 
16 15 1 3

However, the sums \{1,2,3,\dots,26\} are not possible to obtain.