The 64 squares of an 8 × 8 chessboard are filled with positive integers in such a way that each integer is the average of the integers on the neighboring squares. (Two squares are neighbors if they share a common edge or a common vertex. Thus a square can have 8, 5 or 3 neighbors depending on its position). Show that all the 64 integer entries are in fact equal.
Brief Solution : Any given entry must lie in between the smallest and largest entries of its neighbors. Thus, the largest entry on the board must be surrounded by identical entries. This forces all entries to be equal.
Couple of years ago, I got a little cheeky and decided to ask myself what might happen if we take sums instead of averages. Fortunately, I was able to rope in a few equally deranged friends who were as interested as I was in useless problems, and we got a very precise answer to it.
Question : An $n \times n$ chessboard for $n \geq 3$, with each square bearing an integer, is said to be a solution to the neighbor sum problem if each number is the sum of the numbers on the neighboring squares. Two squares are neighbors if they share a common edge or a common vertex. A chessboard with all squares bearing the number zero is said to be a trivial solution. How many such non-trivial solutions exist for a chessboard of given size $n\times n$?
The idea we used to tackle this problem is to imagine a chessboard full of integers and consider the linear transform
$$x \mapsto - x + \sum_{x\sim y} y$$
where $a\sim b$ represents the relation that $a$ is a neighbour of $b$. The kernel of this linear map is precisely the answer to our question.
It turned out that we were lucky and the matrix representing this linear map can be easily studied using theorems that others have proved before (in other words, we let smarter people from the past do the heavy lifting). Using these theorems, it soon became clear to us that an $n\times n$ chessboard admits a non-trivial solution to the neighbour sum problem if and only if there exist $p, q \in \mathbb{N}$ such that
$$\left(1 + 2\cos\left(\frac{p\pi}{n + 1}\right)\right) \left(1 + 2\cos\left(\frac{q\pi}{n + 1}\right)\right) = 2$$
and $1 \leq p, q \leq n$.
Solving this diophantine requires tools from Algebraic Number Theory (which I will not go into in this post) but it turns out that it has a solution if and only if $6\mid (n+1)$. One solution for a $5\times 5$ board is
$$\begin{array}{|c|c|c|c|c|}\hline 1 & 0 & -1 & 0 & 1 \\\hline 1 & 0 & -1 & 0 & 1 \\\hline \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} & \phantom{-}0\phantom{-} \\\hline -1 & 0 & 1 & 0 & -1 \\\hline -1 & 0 & 1 & 0 & -1 \\\hline \end{array}$$
and another is its transpose.
Soon, we realised that these techniques can also be extended to other kinds of more general boards. For example, we proved that non-trivial $m\times n$ chessboards satisfying the neighbor-sum property exist if and only if $2 \mid (m+1)$ and $3 \mid (n+1)$ and that non-trivial $m\times n$ toroidal chessboards satisfying the neighbor-sum property exist if and only if $4 \mid m$ and $6 \mid n$. Of course, the next question to ask is about the dimension of the solution space and that turned out to be more difficult than the first problem. To know more, one can consult our original paper (that has now been accepted in American Mathematical Monthly).
As some of you have already figured out, the more general question to ask is whether it is possible to play the same game on a general graph. This is the question we asked in the first paper and tried to partially answer in a recent preprint where we studied the problem on trees.
Among other things, what we found was an algorithm to test whether a given finite tree satisfies the neighbour sum property. Very briefly, for a given tree and for a fixed (root) vertex $v_0$, we set up the following indexing scheme.
For notational clarity we will use $\bar{r}_l$ to denote a general indexing $r_1,\: r_2,\: \ldots,\:r_l$.
Finally, for a finite tree with a root vertex $v_0$ such that the longest path starting at $v_0$ is of length $k$, we also define
$$S_{1,k}= S_{1,k}(v_0) := \sum_{r_1}\left(1-\sum_{r_{2}}\left(1-\ldots\sum_{r_{k-1}}\left(1-\sum_{r_k} 1\right)^{-1}\ldots\right)^{-1}\right)^{-1}$$
and generally
$$S_{j,k}(\bar{r}_{j-1}) = S_{j,k}(\bar{r}_{j-1}, v_0) := \sum_{r_j}\left(1-\sum_{r_{j+1}}\left(1-\ldots\sum_{r_{k-1}}\left(1-\sum_{r_k} 1\right)^{-1}\ldots\right)^{-1}\right)^{-1}$$
for $1<j\leq k$.
One of our main theorems is that for a finite tree $\mathcal{T}=(\mathcal{V},\:\mathcal{E})$, there exists a pair $(\mathcal{T}, f)$ satisfying the neighbour sum property if and only if there is at least one vertex $v_0\in \mathcal{V}$ such that $S_{1k}(v_0)=1$.
Using this algorithm, we then wrote a code giving us the number of trees on $n$ vertices that satisfies the neighbour sum property and the output was as follows
$$0,1,0,0,1,2,2,6,14,29,63,166,405,977,2481,6530,16757,43534, 115700,308527, 820856, 2205628, 5971743$$
which we have not been able to explain fully. However, we were able to prove that the set of unlabelled trees on $n$ vertices has a positive density subset all of whose elements satisfy the neighbour sum property.
Finally, we also tackled this problem on infinite trees and found a couple of nice results. To know more, the interested reader is suggested to take a look into the two mentioned papers.
No comments:
Post a Comment