<p>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$.)</p>

<p>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.)</p>

CC BY-SA 3.0
2012-01-15T15:44:28.630Z
Oh, good point; I've amended the question to reflect your observation.
ctgPi
CC BY-SA 3.0
2012-01-15T11:08:38.307Z
2012-01-15T11:08:38.307Z
domotorp
<p>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.</p>

<p>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.</p>

<p>Is there any equivalent for <em>rectangular</em> 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.</p>

<p>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 <em>is</em> 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?</p>

CC BY-SA 3.0
2012-01-15T01:24:38.190Z
that's a nice question.
Suresh Venkat
CC BY-SA 3.0
2012-01-15T17:58:56.753Z
I suppose a knight's tour is sufficient. Apparently closed tours always exist when $m,n > 8$ and $mn$ is even.
Timothy Sun
CC BY-SA 4.0
2024-09-16T16:53:14.703Z
Assume $p+q$ is odd.  A lower bound of $\lceil mn/2 \rceil$ on the number of placeable knights is easy: put a knight on each white square (or each black if that's better).  When is this optimal?  Given any matching $M$ in the underlying $mn$-vertex bipartite graph, any independent set can have at most one vertex in each edge of $M$, so has size at most $mn-|M|$.  So $\lceil mn/2\rceil$ is optimal if there is a matching of size $mn-\lceil mn/2\rceil = \lfloor mn/2\rfloor$.  (And by Konig's theorem this is sufficient and necessary.)  BTW if $mn$ is odd no matching has size $\lceil mn/2\rceil$.
Neal Young
<co.combinatorics><matching>
Perfect matchings in a chessboard?
ctgPi
# Perfect matchings in a chessboard?

(Asked by: username_0 on 2012-01-14)

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?

**Tags:** co.combinatorics, matching

> **Comments:**
> **username_1**: that's a nice question.  
> **username_2**: I suppose a knight's tour is sufficient. Apparently closed tours always exist when $m,n > 8$ and $mn$ is even.  
> **username_3**: Assume $p+q$ is odd.  A lower bound of $\lceil mn/2 \rceil$ on the number of placeable knights is easy: put a knight on each white square (or each black if that's better).  When is this optimal?  Given any matching $M$ in the underlying $mn$-vertex bipartite graph, any independent set can have at most one vertex in each edge of $M$, so has size at most $mn-|M|$.  So $\lceil mn/2\rceil$ is optimal if there is a matching of size $mn-\lceil mn/2\rceil = \lfloor mn/2\rfloor$.  (And by Konig's theorem this is sufficient and necessary.)  BTW if $mn$ is odd no matching has size $\lceil mn/2\rceil$.  

---

## 1 answers

### Answer by username_4 on 2012-01-15. Score: 9

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.)

> **Comments:**
> **username_0**: Oh, good point; I've amended the question to reflect your observation.  

---

