Esmeralda has created a special knight to play on quadrilateral boards that are identical to chessboards. If a knight is in a square then it can move to another square by moving 1 square in one direction and 3 squares in a perpendicular direction (which is a diagonal of a $2\times4$ rectangle instead of $2\times3$ like in chess). In this movement, it doesn't land on the squares between the beginning square and the final square it lands on. A trip of the length $n$ of the knight is a sequence of $n$ squares $C1, C2, ..., Cn$ which are all distinct such that the knight starts at the $C1$ square and for each $i$ from $1$ to $n-1$ it can use the movement described before to go from the $Ci$ square to the $C(i+1)$. Determine the greatest $N \in \mathbb{N}$ such that there exists a path of the knight with length $N$ on a $5\times5$ board.
Problem
Source: Lusophon Mathematical Olympiad 2021 Problem 2
Tags: Easy Combinatorics
20.12.2021 22:18
Let's color $5\times5$ board as chessboard such that vertex cells are black. Not that Special Knight can move over only black cells or only white cells. I will prove that max number of moves is $12$. Example: Move like this $(2,4)\rightarrow (3,2) \rightarrow (4,4) \rightarrow (1,4) \rightarrow (4,3) \rightarrow (1,2) \rightarrow (4,1) \rightarrow (3,4) \rightarrow (2,1)\rightarrow (5,2) \rightarrow (2,3) \rightarrow (5,4)$. If this knight moves along black cells, then this knight can't come cell $(3,3)$ and can't go to anywhere from here. So if it visits to here number of moves will be $1$. And if it doesn't visit to this cell it can visit at most $13-1=12$ cells. If it moves along white cells, then we showed that it can visit all of white cells. So max number is $12$
22.05.2023 13:41
Attachments:
