Solution of Magic Matrix

The easiest solution to this problem is based on observations.

Let's start with a matrix containing just values of 1:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Each individual cell makes up a magic submatrix by itself. There are 256 such submatrices. Now try to change every other value into a 2, in a chessboard-like pattern:

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

In this solution, we have fewer 1×1 submatrices, but there is the advantage that any value of 1 can be extended in 4 directions, creating multiple 1×2 and 2×1 submatrices. This approach results in 608 magic submatrices, which is considerably closer to our target.

A natural step is to add larger values. For instance, we can recreate the following 4×4 pattern, resulting in 712 submatrices:

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

A better solution is to use the following pattern instead, where each line/column contains a permutation of [1, 2, 3, 4]:

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1

This generates 832 magic submatrices:

  • 64 submatrices of size 1×1
  • 64 submatrices of size 1×2
  • 56 submatrices of size 1×3
  • 56 submatrices of size 3×1
  • 176 submatrices of size 2×2
  • 208 submatrices of size 1×4
  • 208 submatrices of size 4×1
Questions?

Sponsors Gold