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$
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$ – calcstudent Dec 27 '19 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 '19 at 0:33

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.