13
$\begingroup$

This problem has been bothering me for quite a while now.

Consider an $n\times n$ chessboard, with $n$ being an odd positive integer. In the middle square of the board, a $0$ is placed. Starting with that board, how many ways are there to fill the board up with non-negative integers (greater than or equal to $0$) such that no two squares that share an edge are filled with numbers whose difference is greater than $1$.

The problem is easy to do for $n=3$ by simple casework, and I've found the answer for that case to be $433$, but I am clueless on what to do for larger $n$. Even getting the number of ways for $n=5$ seems very hard.

And, before anyone asks, this problem came from my head, not a book or anything of the sorts, so I don't have any clues to how this can be found.

Thanks!

$\endgroup$
  • 4
    $\begingroup$ This is a nice problem. A (possibly more natural) generalization is to remove the restriction that the labels be non-negative. That way it doesn't matter which cell is "pinned" to $0$ (you're really counting inequivalent labelings with $\mathbb{Z}$, where two labelings are equivalent if they differ by an overall additive constant), and you can consider even $n$ as well. You might try calculating the values for $n=1,2,3,4$ and see if the sequence is in OEIS. $\endgroup$ – mjqxxxx Sep 19 '14 at 15:36
  • $\begingroup$ Hm, that is an interesting extension of the problem. I will try doing that too. Maybe it can lead to a method for solving the original problem. $\endgroup$ – ryagami Sep 19 '14 at 15:39
  • $\begingroup$ Non-negative integers cannot be "less than $0$". $\endgroup$ – barak manos Sep 19 '14 at 16:01
  • 1
    $\begingroup$ @Semiclassical making it a torus will probably make it easier for large $n$. The whole problem start to look like some sort of lattice model one studied in statistical mechanics. $\endgroup$ – achille hui Sep 19 '14 at 16:28
  • 1
    $\begingroup$ @TonyK just the ground state energy itself probably won't help. However, if the partition function (the statistical mechanical one) at finite temperature can be estimated, one can compute the entropy of the system and use it to extract information about the total number of states. $\endgroup$ – achille hui Sep 19 '14 at 16:48
7
$\begingroup$

This is not an answer but a note how to compute the number of ways $\mathcal{N}_n$ for $n = 5$.

We can split the $5\times 5$ board into $8$ right angled triangles. Let us label the states in one of the triangle as follows:

$$\begin{array}{|ccccc|} \hline * & * & * & * & e\\ * & * & * & c & d\\ * & * & 0 & a & b\\ * & * & * & * & *\\ * & * & * & * & *\\ \hline \end{array}$$

It is easy to check given the constraint, there are

  • 5 possibilities for $\verb/ab/$ - $00, 01, 10, 11, 12$.
  • 12 possibilities for $\verb/ce/$ - $00, 01, 02, 10, 11, 12, 13, 20, 21, 22, 23, 24$.

Given any legal combination of $a, b, c, e$, the number of possibilities for $d$ can be counted by brute force. The result is summarized by following table. $$\begin{array}{r|lllll} & & & \verb/ab/ & & \\ \verb/ce/ & 00 & 01 & 10 & 11 & 12\\ \hline 00 & 2 & 2 & 2 & 2 & 1\\ 01 & 2 & 2 & 2 & 2 & 1\\ 02 & 1 & 1 & 1 & 1 & 1\\ 10 & 2 & 2 & 2 & 2 & 1\\ 11 & 2 & 3 & 2 & 3 & 2\\ 12 & 1 & 2 & 1 & 2 & 2\\ 13 & 0 & 1 & 0 & 1 & 1\\ 20 & 0 & 0 & 1 & 1 & 1\\ 21 & 0 & 0 & 1 & 2 & 2\\ 22 & 0 & 0 & 1 & 2 & 3\\ 23 & 0 & 0 & 0 & 1 & 2\\ 24 & 0 & 0 & 0 & 0 & 1\\ \end{array}$$

For the other 7 triangles, it is clear each of them have a similar set of possibilities. If we pick 8 admissible configurations, one for each of the 8 triangles and glue them together. We can construct a legal configuration for the whole board provided the configurations of the triangles match at their boundaries.

A consequence of this is if we define $M_5$ as the $12\times 5$ matrices with entries in above table, the total number of ways for $n = 5$ can be evaluated as a trace!

$$\mathcal{N}_5 = \text{Tr} \left( (M_5^T M_5 )^4 \right) = 178383613 $$

As a double check, for the easier case $n = 3$, the corresponding $M_3$ has entries given by the table:

$$\begin{array}{r|rl} & \quad\rlap{\verb/ a/} & \\ \verb/c/ & 0 & 1\\ \hline 0 & 1 & 1\\ 1 & 1 & 1\\ 2 & 0 & 1 \end{array} $$ This leads to $$\mathcal{N}_3 = \text{Tr}\left( \begin{bmatrix}1 & 1 & 0\\1 & 1 & 1\end{bmatrix} \begin{bmatrix}1 & 1\\1 & 1\\0 & 1\end{bmatrix} \right)^4 = \text{Tr}\begin{bmatrix}2 & 2\\ 2 & 3\end{bmatrix}^4 = 433 $$ as expected.

Notes

  • This way of counting $\mathcal{N}_n$ is inspired by the general technique Transfer-matrix method for solving problems in statistical mechanics. The key is break the configuration into units similar to each other. Compute the possibilities for individual units and represent them as matrices. Finally, convert the original sum into the trace of product of these matrices.
$\endgroup$
  • 1
    $\begingroup$ Note that $c$ and $e$ can't differ by more than $2$, so actually there are only $12$ possibilities for $ce$: $00$, $01$, $02$, $10$, $11$, $12$, $13$, $20$, $21$, $22$, $23$, and $24$. $\endgroup$ – mjqxxxx Sep 19 '14 at 19:12
  • $\begingroup$ @mjqxxxx Hmm... I might have a bug in the program to compute the the matrix. Let me recheck my program. $\endgroup$ – achille hui Sep 19 '14 at 19:19
  • $\begingroup$ @mjqxxxx Oops, I forget to test the $|c-d| \le 1$. It should be fixed now. Thanks for pointing out the mistake. $\endgroup$ – achille hui Sep 19 '14 at 19:29

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.