14
$\begingroup$

Consider the problem of finding the maximum number of knights that can be placed on a chessboard without two of them attacking each other. The answer is 32: it's not too difficult to find a perfect matching (the graph induced by knight moves is bipartite, and there's a perfect matching for a 4 × 4 board), which is obviously a minimum edge cover. It's also not difficult to prove that the answer is $\left\lceil \frac{mn}{2} \right\rceil$ for an $m \times n$ chessboard whenever $m,n \geq 3$: it suffices to show matchings for $3 \leq m,n \leq 6$ and do a bit of induction footwork.

On the other hand, if the chessboard were toroidal and $m, n$ were even, the proof wouldn't even require showing a matching for small boards: the map $(x, y) \rightarrow (x+1, y+2)$ has only even-length cycles so there must be a perfect matching.

Is there any equivalent for rectangular chessboards, i.e. is there any simpler way to show that for sufficiently large $m, n$ there is always a perfect matching of the chessboard? For large boards, the rectangular board and the toroidal board are almost equivalent in the sense that the fraction of missing edges goes to zero, but I'm not aware of any theoretical results that would guarantee a perfect matching in that case.

What if, instead of jumping $(1, 2)$ in either direction, a knight jumped $(2, 3)$ squares in either direction? Or, for that matter, $(p, q)$ squares, with $p+q$ odd and $p, q$ coprime? If there is a simple way of proving that the answer is $\left\lceil \frac{mn}{2} \right\rceil$ for sufficiently large $m, n$ (say, $m, n \geq C(p, q)$), what does $C(p, q)$ look like?

$\endgroup$
  • $\begingroup$ that's a nice question. $\endgroup$ – Suresh Venkat Jan 15 '12 at 1:24
  • $\begingroup$ I suppose a knight's tour is sufficient. Apparently closed tours always exist when $m,n > 8$ and $mn$ is even. $\endgroup$ – Timothy Sun Jan 15 '12 at 17:58
9
$\begingroup$

The answer is NOT $\lceil \frac{mn}2\rceil$ for all large $m, n$ if e.g. $p=6$ and $q=3$. Why? Notice that because of the remainders $\mod 3$ now the graph is the (vertex) disjoint union of three bipartite graphs and from each we can select the bigger half. For example if $m=n=100$, then this way we can place (at least) 5002 knights. (This is because $x+y \mod 6$ has six classes which are in three pairs, the differences between the cardinalities of the pairs is $1,1,2$.)

I do not know what happens if we add the condition that $p$ and $q$ are relative primes. (Note that apart from the 2 divisor this is equivalent to $p+q$ and $p-q$ being relative primes, in fact this is the condition that we need and which also shows that $p+q$ being odd is necessary.)

$\endgroup$
  • $\begingroup$ Oh, good point; I've amended the question to reflect your observation. $\endgroup$ – ctgPi Jan 15 '12 at 15:44

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.