5
$\begingroup$

Can you fill $n ^ 2$ real numbers in the table (grid) of size $n \times n$, which are not all zero, and the number in each field is equal to the sum of the numbers in all the fields with adjacent edges?

What conditions does $n$ have to meet, so that there is such a scheme? If there is a corresponding scheme, how many free variables will be among these $n^2$ numbers?

For example

$$ \begin{array}{|c|c|c|c|} \hline 2 & 1 & 1 & 2 \\ \hline 1 & -2 & -2 & 1 \\ \hline 1 & -2 & -2 & 1 \\ \hline 2 & 1 & 1 & 2 \\ \hline \end{array}$$ or $$\begin{array}{|c|c|c|c|} \hline 0 & 1 & 1 & 0 \\ \hline -1 & 0 & 0 & -1 \\ \hline -1 & 0 & 0 & -1 \\ \hline 0 & 1 & 1 & 0 \\ \hline \end{array}$$

$\endgroup$
4
  • $\begingroup$ Do you mind if I ask where this puzzle is coming from? $\endgroup$
    – user700480
    Dec 17, 2022 at 8:39
  • $\begingroup$ When I browsed Zhihu(a Chinese Q&A community), I met this question. $\endgroup$
    – 138 Aspen
    Dec 17, 2022 at 8:50
  • $\begingroup$ It seems to have been already solved on that community, though I have not checked the proof. If someone has time to check the proof and write it as an answer here, it would be lovely. $\endgroup$
    – user700480
    Dec 17, 2022 at 11:02
  • $\begingroup$ symmetry is an interesting observation... $\endgroup$
    – D S
    Dec 17, 2022 at 12:15

1 Answer 1

3
$\begingroup$

Summary: I have some partial general results, consisting of a lower bound on the dimension of the solution space depending on the value of $n$ modulo $30$. I conjecture that lower bound actually holds with equality.


Determining the complete set of solutions to this problem is equivalent to finding the null space of a certain matrix. Let $M_n$ be the matrix with dimensions $n^2\times n^2$, where $$ M_n(i,j)= \begin{cases} 1 & \text{$i$ is adjacent to $j$} \\ -1 & i=j \\ 0 & \text{otherwise} \end{cases}\hspace{2cm} i,j\in \{1,\dots,n^2\} $$ You need to choose some mapping from $\{1,\dots,n^2\}$ to the grid $\{1,\dots,n\}\times \{1,\dots,n\}$ for the condition "$i$ is adjacent to $j$" to make sense.

Any vector in $\ker M_n$ represents a labeling of the $n\times n$ grid where every entry equals the sum of its neighbors. It is simple enough to use Mathematica to compute this null space for $n\le 30$. This table summarizes the dimensions of the results. You can see that more often than not, there is no nontrivial solution.

Null space has dimension when $n=$                                                                  
$0$ $1, 2, 3, 6, 7, 8, 10, 12, 13, 15, 16, 18, 20, 21, 22, 25, 26, 27, 28, 30$
$2$ $4, 5, 9, 11, 14, 17, 19, 23, 24$
$4$ $29$

Naturally, one would hope for some sort of pattern that allows you to determine the dimension of the null space for any $n\ge 1$. From this limited data, I see no pattern appearing.

Edit: With a bit more thought, we can glean a lot from this data. One of the basis vectors for $n=4$ below has a nice circular pattern, which we see repeated again in $n=9$. In fact, it is clear that this pattern can be extended to all $n$ of the form $5k+4$. Similarly, the pattern in $n=5$ reappears in the basis for $n=11$, and this extends to any $n$ of the form $6h+5$. We have shown that

As long as $n\equiv 4\pmod 5$ or $n\equiv 5\pmod 6$, the solution space has at least two degrees of freedon.

If $n\equiv 29\pmod{30}$, so both these conditions occur, then the solution space is at least $4$ dimensional.

The question is, are these two conditions also necessary? From the data, there is nothing to suggest otherwise, so I conjecture the following:

Conjecture: $$\dim(\ker M_n)\stackrel{?}= \begin{cases} 2 & \text{ if }n\equiv 4\pmod 5,n\not\equiv 5\pmod 6\\ 2 & \text{ if }n\not\equiv 4\pmod 5,n\equiv 5\pmod 6\\ 4 & \text{ if }n\equiv 29\pmod{30} \\ 0 & \text{otherwise} \end{cases}$$

Basis for $n=4$: $$\begin{bmatrix} 1& 0& 0& 1\\ 1& -1& -1& 1\\ 1& -1& -1& 1\\ 1& 0& 0& 1\\ \end{bmatrix} \begin{bmatrix} 0& 1& 1& 0\\ -1& 0& 0& -1\\ -1& 0& 0& -1\\ 0& 1& 1& 0\\ \end{bmatrix}$$
Basis for $n=5$: $$\begin{bmatrix} -1& 0& 1& 0& -1\\ -1& 0& 1& 0& -1\\ 0& 0& 0& 0& 0\\ 1& 0& -1& 0& 1\\ 1& 0& -1& 0& 1\\ \end{bmatrix} \begin{bmatrix} 0& -1& -1& 1& 2\\ 1& 0& -1& 0& 1\\ 1& 1& 0& -1& -1\\ -1& 0& 1& 0& -1\\ -2& -1& 1& 1& 0\\ \end{bmatrix}$$
Basis for $n=9$: $$\begin{bmatrix} 1& 0& 0& 1& 0& -1& 0& 0& -1\\ 1& -1& -1& 1& 0& -1& 1& 1& -1\\ 1& -1& -1& 1& 0& -1& 1& 1& -1\\ 1& 0& 0& 1& 0& -1& 0& 0& -1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ -1& 0& 0& -1& 0& 1& 0& 0& 1\\ -1& 1& 1& -1& 0& 1& -1& -1& 1\\ -1& 1& 1& -1& 0& 1& -1& -1& 1\\ -1& 0& 0& -1& 0& 1& 0& 0& 1\\ \end{bmatrix} \begin{bmatrix} 0& 1& 1& 0& 0& 0& -1& -1& 0\\ -1& 0& 0& -1& 0& 1& 0& 0& 1\\ -1& 0& 0& -1& 0& 1& 0& 0& 1\\ 0& 1& 1& 0& 0& 0& -1& -1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& -1& -1& 0& 0& 0& 1& 1& 0\\ 1& 0& 0& 1& 0& -1& 0& 0& -1\\ 1& 0& 0& 1& 0& -1& 0& 0& -1\\ 0& -1& -1& 0& 0& 0& 1& 1& 0\\ \end{bmatrix}$$
Basis for $n=11$: $$\begin{bmatrix} 1& 0& -1& 0& 1& 0& -1& 0& 1& 0& -1\\ 1& 0& -1& 0& 1& 0& -1& 0& 1& 0& -1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ -1& 0& 1& 0& -1& 0& 1& 0& -1& 0& 1\\ -1& 0& 1& 0& -1& 0& 1& 0& -1& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& -1& 0& 1& 0& -1& 0& 1& 0& -1\\ 1& 0& -1& 0& 1& 0& -1& 0& 1& 0& -1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ -1& 0& 1& 0& -1& 0& 1& 0& -1& 0& 1\\ -1& 0& 1& 0& -1& 0& 1& 0& -1& 0& 1\\ \end{bmatrix} \begin{bmatrix} 0& 1& 1& -1& -2& 0& 2& 1& -1& -1& 0\\ -1& 0& 1& 0& -1& 0& 1& 0& -1& 0& 1\\ -1& -1& 0& 1& 1& 0& -1& -1& 0& 1& 1\\ 1& 0& -1& 0& 1& 0& -1& 0& 1& 0& -1\\ 2& 1& -1& -1& 0& 0& 0& 1& 1& -1& -2\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ -2& -1& 1& 1& 0& 0& 0& -1& -1& 1& 2\\ -1& 0& 1& 0& -1& 0& 1& 0& -1& 0& 1\\ 1& 1& 0& -1& -1& 0& 1& 1& 0& -1& -1\\ 1& 0& -1& 0& 1& 0& -1& 0& 1& 0& -1\\ 0& -1& -1& 1& 2& 0& -2& -1& 1& 1& 0\\ \end{bmatrix}$$

Finally, here is the Mathematica code I used to find this data.

Adj[ x1_, y1_, x2_, y2_] := Boole[Abs[x1 - x2] + Abs[y1 - y2] == 1];
M[n_] := Table[Adj[Mod[k, n], Floor[k/n], Mod[h, n], Floor[h/n]] - Boole[k == h],
               {k, 0, n^2 - 1}, {h, 0, n^2 - 1}]
For[n = 1, n < 20, n++,
  V = NullSpace[M[n]];
  Print["There are ", ToString[Length[V]], " patterns when n = ", n];
  For [i = 1, i <= Length[V], i++,
    pattern = ArrayReshape[V[[i]], {n, n}];
    For[r = 1, r <= n, r++, 
      Print[pattern[[r]]]
      ]
    ]
  ]
$\endgroup$
1
  • $\begingroup$ I made this a community wiki because this is really more of a stream of consciousness partial answer. Anyone is free to edit this, or post their own answer. $\endgroup$ Dec 18, 2022 at 4:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .