Can this table be filled with only zeros?

Question

One step consists of picking two adjacent fields and subtracting the smaller number from those two fields from both of them.Is it possible that this table becomes filled with only zeros? Table looks like this: $$\begin{matrix} 0&1 &2\\ 3&4&5\\ 6&7&8\end{matrix}$$

Answer 1

Hint: $0+2+4+6+8\neq 1+3+5+7.$

---

You can solve the problem starting with:

$$\begin{matrix}-4&-3 &-2\\ -1&0&1\\ 2&3&4\end{matrix}$$

First wipe out the top row, yielding:

$$\begin{matrix}0&0&0\\ 3&3&3\\ 2&3&4\end{matrix}$$

Then two more steps yields:

$$\begin{matrix}0&0&0\\ 3&3&\color{red}0\\ \color{pink}0&\color{pink}1&\color{red}1\end{matrix}$$

Two more easy steps and we're done.

---

Let's define a general version of this game.

Game A

Initial state: We are given an undirected graph $(G,E)$ and map $a:G\to\mathbb Z^{\geq 0}$ giving a numeric value for each node of $G$.

At each turn, select an edge $\{n,n'\}\in E$ with $0<a_n\leq a_{n'}$, and subtract $a_n$ from both $a_n$ and $a_{n'}.$

The game ends when we cannot select any edge, and we win if, at the end state, all $a_n$ are zero.

There is a slight variation of this game, with the same initial condition and final condition, and each turn you select an edge with the same conditions, but what you do after selecting is different:

Game B: At each turn, select an edge $\{n,n'\}\in E$ with $0<a_n\leq a_{n'}$, and subtract $1$ from both $a_n$ and $a_{n'}.$

This is an "easier" game, because when we can win Game A, we can easily win game B, since a turn in game A is just repeated turn in game B.

We can see that, in general, game $B$ is strictly easier. For example, given a triangle graph with node values $a\leq b\leq c$, we get a solution to $A$ only when $a+b=c,$ while we get a solution to game $B$ whenever $a+b+c$ is even and $a+b\geq c.$

However, Game A and game B are equivalent in one case: when $G$ is a bipartite graph. We'll show that in a moment.

Note that in game B, the order that you select edges doesn't really matter. The choices are commutative. If $e\in E$, let $w_e$ be the number of times you chose edge $e.$ Then at the end, you want, for each $n\in G$, that $a_n=\sum_{n\in e\in E} w_e.$ That is, for each node, you want to have subtracted one from node $n$ exactly $a_n$ times.

In game $A$, we can see a solution as a set of values $w_e$ assigned to the edges, with the added property that $P=\{e\mid w_e>0\}$ has no loops.

This is because, after selecting edge $\{n,m\}$, we can no longer select one of the $n,m,$ because one of the nodes got zeroed out, and thus no edge can be selected later that contains that node.

Now, given a weighting on $E$ such that $P$ has no loops and $a_n=\sum_{n\in e\in E} w_e$ for each $n,$ we must have a "leaf" edge in $P$, and we can select any leaf edge $e=\{n,n'\}$ for our first turn, with $n$ the leaf node. Since it is a leaf edge, we have $a_n=w_e$ and $a_{n'}\geq w_e$, and thus $a_n\leq a_{n'}.$ Proceed inward, selecting and removing leaf edges until there are no more edges, and we are done.

Claim: When $G$ is bipartite, Game A and Game B are equivalent.

Proof: All cycles in a bipartite graph have even length.

So, given an edge-weighting that solves game B, any loops in the graph have even length. Given a simple loop, $e_1,\dots,e_{2n}$ starting with $w_{e_1}$ minimal in the loop, we can replace the weights $w_{e_1},\dots,w_{e_{2n}}$ with:

$$0,w_{e_2}+w_{e_1},w_{e_3}-w_{e_1},\dots,w_{e_{2n-1}}-w_{e_1},w_{e_{2n}}+w_{e_1}$$

This doesn't change the value of $\sum_{n\in e\in E} w_e$ for any node $n$, but it removes one loop from $P$ and doesn't create any new ones. Proceed inductively to remove all loops.

So a solution to game $B$ can give us a solution of game $A$.

---

Necessary and sufficient conditions for bipartite graphs

Game $B$ also has a (relatively) simple condition for solutions in a bipartite graph. If $(G,E)$ is a bipartite graph with parts $N_0$ and $N_1,$ then the game has a solution if and only if:

1. $\sum_{n\in N_0} a_n = \sum_{n\in N_1} a_n.$

2. For any set $S\subset N_0$, let $S'$ be the set of elements in $N_1$ that are neighbors to as least one element of $S$. Then we require: $$\sum_{n\in S} a_n \leq \sum_{n'\in S'} a_{n'}$$

This smells like Hall's Marriage Theorem. And indeed it is. The proof amounts to creating a bigger bipartite graph $G'$ with $a_n$ copies of each node $n$, and edges between two nodes if there is an edge between their corresponding nodes in $G$. Then Hall's condition is equivalent to requirement 2 above, and condition 1 requires that the marriage be complete - that all nodes on the right side are covered.

Once you have that pairing in $G'$, we set $w_e$, for each edge $e$ in $G$, equal to the number of pairings in $G'$ that map to $e$ under the obvious map.

---

So we have a necessary and sufficient condition for a solution of the general question.

Checkerboards graphs are bipartite, so we can apply it to the original problem. Requirement 1 nukes your case. There are other examples which satisfy (1) which still fail. For example, the $2\times 5$ grid:

$$\begin{matrix}1&\color{red}1&0&0&1\\\color{red}1&0&0&1&1\end{matrix}$$

satisfies (1), but fails to have a solution because the red values add up to $2$ and their neighbors add up to $1$.

Or the $1\times 4$ grid: $$\begin{matrix}\color{red}4&2&1&3\end{matrix}$$

The value $4$ has one neighbor of value $2$.

You can't have anywhere in your diagram something which looks like:

$$\begin{matrix}&&2&\\ &1&\color{red}3&0\\ 2&\color{red}3&0&\\ &0&&\end{matrix}$$

because $3+3>2+1+2$.

The general question of whether a checkerboard with numbers attached has a solution is at least as hard as the case where all the $a_i\in\{0,1\}$, which is equivalent to the question about what subsets of a checkerboard can be covered by dominoes. I seem to recall seeing extensive writing about this somewhere online, but I can't seem to find it.