1
$\begingroup$

The premise is simple. We get a n*n matrix with numbers ranging from 0 to 16. The matrix is the result of a minesweeper-kind of addition whereby we have an original matrix containing numbers ranging from 0 to 3 and the second matrix is none else than the sum of the surrounding cells od the first matrix, wrapping around (i.e. $c_{0\_0}$ = $c_{0\_1}$ + $c_{1\_1}$ $c_{1\_0}$ + $c_{1,2\_0}$ + $c_{0\_2}$ + $c_{2\_2}$ + $c_{0\_0}$ + $c_{2\_0}$

Example:

1 2 3
0 1 3
3 2 1

yields

15 14 13
16 15 13
13 14 15

How would you go about solving this mathematically for squares of arbitrary size 0 <= n < 100?

To clarify: the goal is to get the original matrix (shown first, containing only $0,1,2,3$) from the second matrix.

$\endgroup$
  • 1
    $\begingroup$ I believe "solving this" is finding the original matrix by the result? If that's so, you should specify it. $\endgroup$ – Thomas Blue Sep 25 '19 at 10:10
  • $\begingroup$ clarified, thanks. $\endgroup$ – S. L. Sep 25 '19 at 10:13
1
$\begingroup$

Partial answer

Edit: Jaap Scherphuis made a insightful comment to show that

Solving this matrix uniquely is not always possible when $n$ is even

Reasoning

Consider the following matrix.

 12 12 12 12
 12 12 12 12
 12 12 12 12
 12 12 12 12
 
One solution for this is as follows
 0 1 2 3
 1 2 3 0
 2 3 0 1
 3 0 1 2
 
However, another perfectly valid solution is this
 1 3 0 2
 3 0 2 1
 0 2 1 3
 2 1 3 0
 
This is due to the fact that the set of simultaneous equations governing the $n=4$ solution are not linearly independent (the rank of the matrix associated to the system is less than $16=n^2$).

This is the case whenever $n$ is even. As Jaap Scherpuis pointed out you could always use a checkerboard pattern using any distinct values for the two colours. For example, in the case $n=6$, we could have
 0 3 0 3 0 3
 3 0 3 0 3 0
 0 3 0 3 0 3
 3 0 3 0 3 0
 0 3 0 3 0 3
 3 0 3 0 3 0
 
or we could have
 1 2 1 2 1 2
 2 1 2 1 2 1
 1 2 1 2 1 2
 2 1 2 1 2 1
 1 2 1 2 1 2
 2 1 2 1 2 1
 
and both give rise to the grid
 12 12 12 12 12 12
 12 12 12 12 12 12
 12 12 12 12 12 12
 12 12 12 12 12 12
 12 12 12 12 12 12
 12 12 12 12 12 12
 
so this result grid does not have a unique solution.

For the other cases

There is an obvious strategy of inverting the system of simultaneous equations but this is quite difficult when $n$ is large (perhaps there is a clever shortcut to find the inverse of such large matrices). In any case, the matrix associated to the system of simultaneous equations seems to always be invertible when $n$ is odd (checked for a few small cases) so the solution is always uniquely determined (even among the reals).

For the case $n=3$

We find that each entry is the sum of all other elements except for the entry in the same position. Hence, if are given a matrix, the strategy would be to take each entry away from its maximum value. Then, check if this is the solution and, if not, add 1 to each entry and check again until the solution is obtained.

For example

In the case given in the question the given matrix is

 15 14 13
 16 15 13
 13 14 15
 
The maximum value is 16, and if we take all entries in the matrix away from 16, we get
 1 2 3
 0 1 3
 3 2 1
 
which is the solution.
Alternatively, if the given matrix were
 16 16 16
 16 16 16
 16 16 16
 
Then taking each entry from the maximum value yields
 0 0 0
 0 0 0
 0 0 0
 
which is not the solution, so we add 1 to each entry to get
 1 1 1
 1 1 1 
 1 1 1
 
which is again not the solution, but if we add 1 more we get
 2 2 2
 2 2 2 
 2 2 2
 
which is the solution.

$\endgroup$
  • 2
    $\begingroup$ A checkerboard is a nice counter example for even $n$ (use any two distinct values for the two colours). $\endgroup$ – Jaap Scherphuis Sep 25 '19 at 11:29
  • $\begingroup$ @JaapScherphuis Ah, yes of course, I have way overcomplicated this, haven't I? $\endgroup$ – hexomino Sep 25 '19 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.