Konstantin moves a knight on a $n \times n$- chess board from the lower left corner to the lower right corner with the minimal number of moves. Then Isabelle takes the knight and moves it from the lower left corner to the upper right corner with the minimal number of moves. For which values of $n$ do they need the same number of moves?
Problem
Source: Bundeswettbewerb Mathematik 2020, Round 1 - Problem 2
Tags: combinatorics, combinatorics proposed, chess board, Chess knight
11.04.2021 18:01
For $n=1$, both need zero moves and for $n=2$, neither of them can move the knight to the respective corner. Let now $n\geq 3$. By considering the usual colouring of the chess board,we see that $n$ must be odd, because in every move the knight moves from black to white and vice versa. However, if $n$ was even, the upper right corner and the lower right corner have opposite colours, contradiction. We now want to obtain some bound for $n$. If $4|n-1$, Konstantin needs at most $\frac{n-1}{2}$ moves. He alternately moves the knight two fields right and one field up and two fields right and one field down. If $4 \nmid n-1$, Konstantin needs at most $\frac{n+1}{4}$ moves. Firstly, he moves the knight two fields up and one field right and then he moves two fields down and one field right. Then he can proceed as above and performs $\frac{n-3}{4}$ moves to end up and the lower right corner. On the other hand, Isabelle must move her knight at least $\frac{n-2}{3}$ times,since the knight has to go from $(1,1)$ to $(n,n)$ and in every move the coordinates can increase by $3$ at most. Thus if $n$ is a solution to the problem, we must have $\frac{2n-2}{3}\leq \frac{n+1}{2}\Leftrightarrow n\leq 7$. It is easy to see that $n=3$ and $n=5$ are no solutions. For $n=7$, both players need $4$ moves: Isabelle alternates between moving her knight two fields right and one field up and two fields up and one field right. Kosntantin lternately moves the knight two fields right and one field up and two fields right and one field down.