A knight is placed on each square of the first column of a $2017 \times 2017$ board. A move consists in choosing two different knights and moving each of them to a square which is one knight-step away. Find all integers $k$ with $1 \leq k \leq 2017$ such that it is possible for each square in the $k$-th column to contain one knight after a finite number of moves. Note: Two squares are a knight-step away if they are opposite corners of a $2 \times 3$ or $3 \times 2$ board.
Problem
Source: Mexico National Olympiad 2017, Problem 1
Tags: combinatorics, board, knight
06.11.2017 23:49
If we color in chess order, we can notice, that number of black cells with knights is always odd. But $2i$-column has even number of black cells - so impossible. For odd $k$ it is enough to prove for $k=3$ Let $(a,b)$ - is column and row of knight. And $(a,b)\to (c,d)$ is move 1) $(1,1)\to (2,3),(1,2)\to (2,4)$ 2) $(2,3) \to (3,1), (1,3) \to (2,5)$ 3)$(2,4) \to (3,2), (2,5) \to (3,3)$ Next moves are $(1,2i) \to (3, 2i+1), (1,2i+1) \to (3,2i)$ So for $k=3$ it is possible, but it means that possible for $k=2i+1$
18.04.2021 00:37
The answer is $k$ odd. Color in the board like a chessboard such that the grids alternate black and white. WLOG, let the first column have $1009$ white squares and $1008$ black squares. So, the knights are on $1009$ white squares and $1008$ black squares initially. To see that $k$ even is not possible, observe that after a move the parity of the number of white and black squares is invariant. Hence $k$ even is impossible since for $k$ even there are $1008$ white squares and $1009$ black squares. Now I will prove that $k$ odd is possible. Lemma: Given a $3 \times 3$ grid and 3 knights in the left column, it's possible to move all of them to the rightmove column in a number of moves. Proof: 1. $(1,1) \rightarrow (2,3), (1,3) \rightarrow (2,1)$. 2. $(1,2) \rightarrow (3,3), (2,3) \rightarrow (3,1)$. 3. $(2,1) \rightarrow (1,3), (3,3) \rightarrow (2,1)$. 4. $(1,3) \rightarrow (3,2), (2,1) \rightarrow (3,3)$. Done. This lemma tells us that given 3 rows and $k$ columns where $k$ is odd, it's possible to move the knights from the first column to the $k$th column using only squares in those 3 rows. Since $2016$ is divisible by $3$, it's possible to move the knights in the first 2016 rows to any column $k$ where $k$ is odd. For the last knight, just move it from $(i,j) \rightarrow (i+1, j+2) \rightarrow (i+2, j)$ until it reaches the desired column. The other knight move can be some random knight move.
11.09.2022 16:39
Consider the coloring $x+y\pmod 2.$ We must have a starting parity of #black as $0,$ and if $k$ is even, we end at $1.$ However, every knight changes color every move, so the sum of colors of two knights must stay same parity. Thus, $k$ must be odd. We can now move to safety ($k=3$) on a $3\times 5$ board. a5 b5 c5 a4 b4 c4 a3 b3 c3 a2 b2 c2 a1 b1 c1 1. N1b3 N2c1 2. Nbc5 N3c2 3. N4c3 Na5c4 Now, if we move to safety $1-5,$ we can pair up $6-7, \dots 2016-2017$ by doing: a7 b7 c7 a6 b6 c6 1. N7c6 N6c7 Thus we can do $k=3,$ or move everything right by one space. We can do this for all odd $k.$