Posted by: yanzhang | July 27, 2009

Knights on Tori

(guest post by Joel Lewis, another of my office-mates. -Y)

————-

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.

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

(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.) 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 this blog’s proprietor): 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.

– Joel Lewis

Advertisements

Responses

  1. First, I wanted to thank Yan for suggesting I write and then posting this post (and also for letting me waste his quals-studying time with these puzzles).

    Second, I should point out that I made one mildly misleading statement: the 4 \times 4 regular chessboard is non-Hamiltonian (and there’s a more transparent way to prove it: consider the squares (1, 1), (2, 3), (3, 2) and (4, 4)), but the 4 \times 4 torus chessboard actually does have a Hamiltonian cycle.

  2. Yeah, I was going to point out that the toroidal board does have a Hamiltonian cycle.

    Incidentally, there’s no need to use a Hamiltonian cycle on doubly-even-sized boards. You can easily split up the board into pairs of squares that attack each other. Clearly at most one of each pair can be occupied.

    Good post!

  3. Hi Boris,

    Thanks for the kind words! Yes, you’re absolutely right that the Hamiltonian path argument is unnecessary. However, I don’t know a good way to show the uniqueness of the white or black squares as maximal independent sets without using the knight’s tour.

  4. I feel uniqueness follows from the fact that anytime you get out of a white/black square you can get back in one jump, not that you need a complete tour.

  5. But on the 4 \times 4 board (where everything else seems to be the same) there are other maximizing sets — for example, the first and fourth rows together are an independent set of (maximal) size 8.

  6. oh hmm. my argument doesnt work

  7. There you are, Joel! I went to school with you, remember? I’m glad to see you still in math. I’ve departed from the subject, but I still have a fondness for it. We ought to meet up sometime, if you’re interested. Thanks.

    Anton

  8. […] this entry began “Intro poset.”  I have a webpage.  I have actually already written one post on this blog.  I don’t know what sorts of other posts I will write here, but they will […]


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

Categories

%d bloggers like this: