Knights on Tori

(ed. note: this post is back-dated; it was actually posted here May 1, 2011.)

I frequent the Art of Problem Solving forum (also knows as MathLinks) where at some point I stumbled across the following problem (advertised (.pdf) as appearing on the 1996 Iranian Mathematical Olympiad, a claim I have no reason to doubt but no way to verify):

Consider a chessboard in which the opposite edges have been identified to yield a torus. What is the maximal number of knights that can be placed on this board so that no two attack each other?

There are several ways to attack this problem. If you’ve spent some time thinking about chess-related mathematics, you’re probably familiar with the existence of a knight’s tour on a (regular) chessboard: it’s possible to start with a knight on any square of the chessboard and make a sequence of 64 moves so that it visits every square exactly once before returning to its original position. It follows that we can place at most 32 knights on the board so that no two attack each other: no two squares visited consecutively in the knight’s tour may both be occupied, so at most half of the board may be covered. Moreover, it’s easy to find a set of 32 squares on which we can place the knights — for example, the 32 black squares do nicely, since a knight on a black square attacks only white squares. (In fact, one can extend this argument to show that this and the 32 white squares are the only sets of 32 squares on which we can place nonattacking knights.)

That was a regular chessboard — we still haven’t dealt with the torus. Note that when we identify edges, we can’t possibly increase the number of knights that fit on the board. Also, it is still true on the torus that knights on black squares attack only black squares. Thus 32 squares are still maximal, and we’ve answered our question.

To summarize what we’ve done using the terminology of graph theory, we’ve used the Hamiltonicity of the knight’s graph on an 8 \times 8 chessboard, the fact that the knight’s graph is bipartite, and the fact that adding extra edges to a graph can only decrease its independence number. This Hamiltonicity result is reasonably high-powered, though. Let’s try to avoid using it. One way to do this might be to start with a non-Hamiltonian board, for example, the 4 \times 4 board.  (Showing that this board is non-Hamiltonian is perhaps nontrivial — one way to do this is by using the contrapositive of the parenthetical statement two paragraphs back.)1

Consider a 4 \times 4 chessboard in which the opposite edges have been identified to yield a torus. What is the maximal number of knights that can be placed on this board so that no two attack each other?

4by4

What do we do now? One way to proceed is by a clever counting argument: on the 4 \times 4 toroidal knight’s graph, every vertex has degree four. Thus, each knight attacks four squares while each non-knight square is attacked by at most four knights. It follows that the number of knights can be no more than the number of non-knight squares and so eight squares is maximal. Once again, the toroidal board is bipartite and we can fill all the white squares with knights to achieve our bound.

(By the way, for those who are interested, the toroidal 4 \times 4 knight’s graph is isomorphic to the skeleton of the four-dimensional hypercube. I guess there just aren’t that many four-regular symmetric bipartite graphs on sixteen vertices.)

This latter argument is very elegant. It also has a lot of power: we can use it to show that we can always fit 2n^2 nonattacking knights on a toroidal 2n \times 2n board. Note, however, that if the side-length of the board is odd, bad things start to happen: the square in the upper-left corner attacks squares along the bottom and right edges of the board that are (under the usual chessboard coloring) the same color, so we can’t achieve the same maximum that we can with a regular board. In general, it seems difficult to nail down precisely what the largest number of knights is for such a board. However, some cases are still amenable to our methods. In particular, the following question allows a quite beautiful solution:

Consider a 5 \times 5 chessboard in which the opposite edges have been identified to yield a torus. What is the maximal number of knights that can be placed on this board so that no two attack each other?

Note that this graph is very much nonbipartite. For example, the vertices in positions (1, 2), (3, 3) and (5, 4) form a triangle. So, we have to lower our expectations for the size of the independent set we’re looking for — maybe we can only fit eight knights on the board, instead of thirteen. But a little experimenting shows that this is overly optimistic — while it’s easy to fit five knights on the board (any row or column will do), even putting a sixth down is quite difficult.

A little more experimentation yields the following remarkable fact: not only does our graph contain triangles, but it actually contains a large number of five-cliques! For example, if we place a knight at the center of the board and choose “every other” square from those it attacks (so, the squares (1, 4), (2, 1), (3, 3), (4, 5) and (5, 2)) we have five mutually-attacking squares. This leads immediately to two possible solution methods (one found by my student K. Cordwell, the other by my friend Y. Zhang): we can either note that each knight attacks eight squares while each non-knight square may be attacked by at most two knights (since the eight squares potentially attacking the given square decompose into two copies of K_4, and we may have at most one knight on each copy) so at most one fifth of the board may be occupied by knights, or we may note that we can cover the board by five disjoint shifts of the K_5 mentioned above and so choose at most one knight from each copy.

5by5

For those who are interested in this sort of thing, Noam Elkies and Richard Stanley have a nice paper titled The Mathematical Knight (.pdf) that’s worth a read. Also, there’s John J. Watkins’ extremely readable Across the Board (the first chapter is available free there) which is, I guess, a textbook for a course on graph theory viewed completely through the lens of chess problems. Also, I gather that some people actually enjoying playing chess, rather than solving math problems motivated by it. This website proposes a starting position to play toroidal chess on a conventional 8 \times 8 board.

[fn1] This statement is slightly misleading: while a 4 \times 4 regular chessboard isn’t Hamiltonian (here’s a more transparent way to prove it: consider the squares (1, 1), (2, 3), (3, 2) and (4, 4)), the 4 \times 4 torus chessboard actually is Hamiltonian.

Advertisements
This entry was posted in Combinatorics and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s