Revision history [back]

I found the following recreational mathematics problem too hard for me. Can anyone give me hints how to find a solution?

Consider the $4\times 4$ matrices with integer coefficients. Let its elements be $a_{i,j}$ for $1\leq i,j\leq 4$. Now form a four sets $A_1,A_2,A_3,A_4$. Say that $A_1$ is the set of element $a_{i,j}$. Also, $A_2$ is the set of elements $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+2}$ i.e. if you think matrix, $A_2$ is like sum of elements of $2\times 2$-subsquares of the matrix. Similarly, denote $A_3$ the set of sums of $3x3$-submatrices and $A_4$ the sum of elements of the given $4\times 4$-matrix.

Now, I heard a rumor that one can give an example for 16 integers $a_{i,j}$ such that all integers from 1 to 25 belongs to $A_1\cup A_2\cup A_3\cup A_4$. How can one find such an example? It is easy to see that at least some of the elements $a_{i,j}$ must satisfy $1\leq a_{i,j}\leq 25$ but there is still too many element that finding such a matrix by brute force seems impossible. I was wondering if genetic algorithm or simulated annealing works for such a problem but I don't have enough experience to implement that.

The best I know is that solution for case 24 is possible:

-42  22  23   7
 13  11 -32  14
-23  16  15   8
 19   9 -22   1

I found the following recreational mathematics problem too hard for me. Can anyone give me hints how to find a solution?

Consider the $4\times 4$ matrices with integer coefficients. Let its elements be $a_{i,j}$ for $1\leq i,j\leq 4$. Now form a four sets $A_1,A_2,A_3,A_4$. Say that $A_1$ is the set of element $a_{i,j}$. Also, $A_2$ is the set of elements $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+2}$ i.e. if you think matrix, $A_2$ is like sum of elements of $2\times 2$-subsquares of the matrix. Similarly, denote $A_3$ the set of sums of $3x3$-submatrices and $A_4$ the sum of elements of the given $4\times 4$-matrix.

Now, I heard a rumor that one can give an example for 16 integers $a_{i,j}$ such that all integers from 1 to 25 belongs to $A_1\cup A_2\cup A_3\cup A_4$. How can one find such an example? It is easy to see that at least some of the elements $a_{i,j}$ must satisfy $1\leq a_{i,j}\leq 25$ but there is still too many element that finding such a matrix by brute force seems impossible. I was wondering if genetic algorithm or simulated annealing works for such a problem but I don't have enough experience to implement that.

The best I know is that solution for case 24 is possible:

-42  22  23   7
 13  11 -32  14
-23  16  15   8
 19   9 -22   1

I found the following recreational mathematics problem too hard for me. Can anyone give me hints how to find a solution?

Consider the $4\times 4$ matrices with integer coefficients. Let its elements be $a_{i,j}$ for $1\leq i,j\leq 4$. Now form four sets $A_1,A_2,A_3,A_4$. Say that $A_1$ is the set of element $a_{i,j}$. Also, $A_2$ is the set of elements $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+2}$ i.e. if you think matrix, $A_2$ is like sum of elements of $2\times 2$-subsquares of the matrix. Similarly, denote $A_3$ the set of sums of $3x3$-submatrices $3\times 3$-submatrices and $A_4$ the sum of elements of the given $4\times 4$-matrix.

Now, I heard a rumor that one can give an example for 16 integers $a_{i,j}$ such that all integers from 1 to 25 belongs to $A_1\cup A_2\cup A_3\cup A_4$. How can one find such an example? It is easy to see that at least some of the elements $a_{i,j}$ must satisfy $1\leq a_{i,j}\leq 25$ but there is still too many element that finding such a matrix by brute force seems impossible. I was wondering if genetic algorithm or simulated annealing works for such a problem but I don't have enough experience to implement that.

The best I know is that solution for case 24 is possible:

-42  22  23   7
 13  11 -32  14
-23  16  15   8
 19   9 -22   1

I found the following recreational mathematics problem too hard for me. Can anyone give me hints how to find a solution?

Consider the $4\times 4$ matrices with integer coefficients. Let its elements be $a_{i,j}$ for $1\leq i,j\leq 4$. Now form four sets $A_1,A_2,A_3,A_4$. Say that $A_1$ is the set of element $a_{i,j}$. Also, $A_2$ is the set of elements $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+2}$ i.e. if you think matrix, $A_2$ is like sum of elements of $2\times 2$-subsquares of the matrix. Similarly, denote $A_3$ the set of sums of $3\times 3$-submatrices and $A_4$ the sum of elements of the given $4\times 4$-matrix.

Now, I heard a rumor that one can give an example for 16 integers $a_{i,j}$ such that all integers from 1 to 25 belongs to $A_1\cup A_2\cup A_3\cup A_4$. How can one find such an example? It is easy to see that at least some of the elements $a_{i,j}$ must satisfy $1\leq a_{i,j}\leq 25$ but there is still too many element that finding such a matrix by brute force seems impossible. I was wondering if genetic algorithm or simulated annealing works for such a problem but I don't have enough experience to implement that.

The best I know is that solution for the case 24 is possible:

-42  22  23   7
 13  11 -32  14
-23  16  15   8
 19   9 -22   1

I found the following recreational mathematics problem too hard for me. Can anyone give me hints how to find a solution?

Consider the a $4\times 4$ matrices matrix with integer coefficients. Let its elements be $a_{i,j}$ for $1\leq i,j\leq 4$. Now form four sets $A_1,A_2,A_3,A_4$. $A_1$, $A_2$, $A_3$, $A_4$. Say that $A_1$ is the set of element elements $a_{i,j}$. Also, $A_2$ is the set of elements $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+2}$ $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}$ i.e. if you think matrix, $A_2$ is like sum the set of sums of elements of $2\times 2$-subsquares of the matrix. Similarly, denote by $A_3$ the set of sums of $3\times 3$-submatrices and $A_4$ the set containing the sum of all elements of the given $4\times 4$-matrix.

Now, I heard a rumor that one can give an example for of 16 integers $a_{i,j}$ such that all integers from 1 to 25 belongs to $A_1\cup A_2\cup A_3\cup belong to $A_1 \cup A_2 \cup A_3 \cup A_4$. How can one find such an example? It is easy to see that at least some of the elements$a_{i,j}$must satisfy$1\leq a_{i,j}\leq 25$ but there is are still too so many element elements that finding such a matrix by brute force seems impossible. I was wondering if genetic algorithm algorithms or simulated annealing works work for such a problem but I don't have enough experience to implement that.

The best I know is that solution for the case getting all integers from 1 to 24 is possible:possible, for instance using the matrix:

-42  22  23   7
 13  11 -32  14
-23  16  15   8
 19   9 -22   1