3
$\begingroup$

Consider a chessboard infinite in positive x and y directions, all square has non-negative integer coordinates, and the only corner is at $(0,0)$. A $(p,q)$-knight is a piece that can move so that after each move one of the coordinate change by $p$ and the other change by $q$ (we will just call it a knight from now on). Set a knight at the corner $(0,0)$, and assume that $(p,q)$ is such that every position on the board can be reached by the knight.

For a position $(m,n)$ on the board, let $d(m,n)$ be the minimum number of moves needed for a knight from the corner to reach $(m,n)$.

Now the following claims are true:

$\gcd(p,q)=1$ and $p,q$ are not both odd. This is necessary and sufficient conditions for every square to be reachable. Necessary is easily seen, for sufficient a sketch of the solution is in this question Can an $(a,b)$-knight reach every point on a chessboard?

For every square on the board, every ways to reach it require the number to moves to have the same parity as $m+n$, this is from black-white coloring. So $d(m,n)$ has the same parity as $m+n$

$d(m,n)\max(p,q)>=\max(m,n)$, obviously.

$d(m,n)(p+q)>=m+n$

So let's $B(m,n)$ be the smallest integer that satisfy all the constraints: $B(m,n)\max(p,q)>=\max(m,n)$ and $B(m,n)(p+q)>=m+n$ and $B(m,n)$ has the same parity as $m+n$. Then we know that $d(m,n)>=B(m,n)$ for all $(m,n)$. We make $B(m,n)$ the predicted value of $d(m,n)$.

DEFINITION: An "awkward spot" on the board is a position $(m,n)$ in which $d(m,n)$ is not equal to $B(m,n)$.

QUESTION: is it true that for all valid values of $(p,q)$ then the number of awkward spots are finite?

Example: for the normal chess knight $(p,q)=(1,2)$ then you can check against this answer chess board knight distance (but need some small modification since we start from a corner) to see that the awkward spots are $(0,1),(1,0),(1,1),(2,2)$ so there are only a finite number of them.

(I have heard suggestions to use Fourier transform but I have no clues what to do with it)

$\endgroup$

1 Answer 1

3
$\begingroup$

If I understand you correctly, the number of "awkward spots" can easily be infinite. This is mainly because, in a sense, your definition of $B(m,n)$ is a bit too "optimistic".

Consider $(p,q) = (1,10)$.

Obviously any square $(k, 10k)$ can be reached in exactly $k$ moves. What about $(k, 10k-2)$, for $k \ge 1$? We have $B(k, 10k-2) = k$ because:

  • $k \max(1,10) = 10k \ge \max(k,10k-2) = 10k-2$

  • $k (1 + 10) = 11k \ge k + (10k-2) = 11k - 2$

  • $k$ has same parity as $k + (10k-2)$

  • OTOH $(k-1) (1 + 10) = 11(k-1) < 11k -2$

However, the square $(k, 10k-2)$ cannot be reached in $k$ moves (or fewer for that matter), because:

  • If all $k$ moves are of the form $(\pm 1, +10)$ then the final $y$-coordinate would be $10k$ and not $10k-2$.

  • If at least one move is not $(\pm 1, +10)$ then the final $y$-coordinate is at most $10(k-1) + 1 = 10k -9 < 10k-2$.

Conclusion: For the $(1,10)$-knight, $(k, 10k-2)$ (and many similar squares) are awkward for any $k \ge 1$.


Further thoughts: in general for a $(p,q)$-knight to move to row $r$ (regardless of column) already requires something like solving the Bezout identity $px + qy = r$ with "minimum" coefficients $(x,y)$, in a sense. My example shows that forgetting this bound already makes your $B(m,n)$ too optimistic. A more interesting question is if you somehow include this in the definition of $B(m,n)$, then are there infinite number of awkward squares? I don't know the answer to that question.

$\endgroup$
2
  • $\begingroup$ This looks correct, thanks. Interesting, it looks like this problem is even harder than I thought. Perhaps this formula only work for a few small value of $(p,q)$. Maybe I should think about this some more. $\endgroup$ Dec 27, 2019 at 0:28
  • 1
    $\begingroup$ It seems even including the Bezout condition is insufficient. E.g. the $(1,10)$-knight needs $5$ moves to reach row $y=5$, or reach column $x=5$, but what is $d(5,5)$? By your original definition, $B(5,5) = 1$. If you include the Bezout condition, you might say $B'(5,5) = 5$. But it cannot reach $(5,5)$ in $5$ steps, because to reach $y=5$ row it must do $(\pm 10, +1)$ five times. Now this isn't to say the number of awkward spots (w.r.t. new $B'(m,n)$) is still infinite. But I do think a general logic for $d(m,n)$ is very interesting, and possibly very hard... at least for me. :) $\endgroup$
    – antkam
    Dec 27, 2019 at 0:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .