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. Those are form \begin{matrix} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}\\ \end{matrix} Let us say that its $1\times 1$ subsquares are the elements of the matrix i.e. the set $A_1=\{a_{i,j}|1\leq i,j\leq 4\}$. Similarly, the set of $2\times 2$ subsquares is the set $A_2=\{ a_{i,j} + a_{i+1,j} + a_{i,j+1}+a_{i+1,j+1}| 1\leq i,j\leq 3\}$, the set of $3\times 3$ subsquares is the set $A_3=\{ a_{i,j} + a_{i+1,j} + a_{i+2,j}+a_{i,j+1} + a_{i+1,j+1} + a_{i+2,j+1}+a_{i,j+2} + a_{i+1,j+2} + a_{i+2,j+2}| 1\leq i,j\leq 2\}$ and $A_4$ is just the sum of elements of a matrix. Now, I heard a rumour that one can give an example for 16 integers $a_{i,j}$ such that $\{1,2,\ldots,25\}\subset 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.