A chess knight has injured his leg and is limping. He alternates between a normal move and a short move where he moves to any diagonally neighbouring cell. The limping knight moves on a $5 \times 6$ cell chessboard starting with a normal move. What is the largest number of moves he can make if he is starting from a cell of his own choice and is not allowed to visit any cell (including the initial cell) more than once?
Problem
Source: Baltic Way 2017, Problem 8
Tags: combinatorics, combinatorics proposed, Chess knight, Chessboard
ABZH
23.01.2018 08:29
Maximum move is 25
A-Thought-Of-God
11.11.2020 16:17
ABZH wrote: Maximum move is 25 Do you have a proof? @below thanks!
Tintarn
13.11.2020 12:42
A-Thought-Of-God wrote: Do you have a proof?
colour the second and fourth row red and note that if we denote the cells of the knight by $0,1,2,3,\dots$, then between $2k-1$ and $2k$ he makes a shot move so that exactly one of the two cells is red. But there are only $12$ red cells, so $k \le 12$ and we are done.
normalerliu
26.02.2022 09:51
Tintarn wrote: colour the second and fourth row red and note that if we denote the cells of the knight by $0,1,2,3,\dots$, then between $2k-1$ and $2k$ he makes a shot move so that exactly one of the two cells is red. But there are only $12$ red cells, so $k \le 12$ and we are done. I just constructed an example of 26. Actually, your proof reveals that exactly one of (1,2) is red, one of (3,4) is red, ..., and one of (23,24) is red, but 0 and 25 are not necessarily red or not. The maximum move should be 26 modified: Oh sorry, you are right, 25 moves means 26 positions. My fault.
ZETA_in_olympiad
26.02.2022 10:23
@above I don't understand the reason for revive.