Olympiad Mathematics Again

Mexican columns of knights, 2017

August 31, 2019

Problem. There is a board 2017×2017. Initially, 2017 knights (chess pieces) are located in the first column, one knight in each cell. A move consists of choosing two distinct knights and moving both of them simultaneously (as a knight is permitted to move in chess). Find all possible integer values of k, 1k2017, such that it is possible to reach a position after a finite number of moves where all 2017 knights are located in column k, one knight in each cell.

Origin: Mexico National Mathematical Olympiad (Olimpiada Mexicana de Matemáticas, Concurso Nacional) 2017, problem 1.

Solution. Consider the standard chessboard coloring in black and white. Let's assume that the corners of the board are colored black. Then the first column has 1008 white cells and 1009 black cells.

Observe that in a standard chess move of a knight, it changes the color of the cell (that is, a knight always goes from a white cell to a black cell or from a black cell to a white cell, but never from a white cell to a white cell and never from a black cell to a black cell). Therefore, one knight move changes the parity of the number of knights on white cells. And two simultaneous knight moves (comprising a move in the problem setting, which we will call a \emph{paired move}) preserves this parity. This means that after any number of such paired moves, the parity of the number of knights on white cells stays always the same, and is equal to this parity at the beginning. At the beginning, we have 1008 knights on white cells, an even number. So, this number always stays even.

But notice that only the odd columns have even number of white cells (1008); and the even columns have odd number of white cells (1009). Therefore, after any number of paired moves, the knights can not be located in an even column, one knight in each cell. So, the even columns are impossible positions of the knights, and thus even k should be excluded from the answer.

Now let's show that for the odd columns, the positions are in fact possible. We will show how to move the knights from the first column to the third one whithout stepping outside of the first three columns. From that it would follow that in the same manner, we can move the knights from the third column to the fifth, and so on.

So, for the 2014 knights in the cells (1,1), (1,2), \ldots, (1,2014), we divide them in pairs, and for each pair in the cells (1,2i1) and (1,2i), 1i1007, we execute the following two paired moves:

  1. (1,2i1)(2,2i+1) and (1,2i)(2,2i+1);
  2. (2,2i+1)(3,2i1) and (2,2i+1)(3,2i).
As a result of these two paired moves, the knights in the cells (1,2i1) and (1,2i) move to the cells (3,2i1) and (3,2i), that is, they move to the same rows as they were but in the third column.

The paired moves for the pair of knights in the cells (1,2015) and (1,2016) are similar, but with a different intermediate position so that not to step outside of the board:

  1. (1,2015)(2,2013) and (1,2016)(2,2014);
  2. (2,2013)(3,2015) and (2,2014)(3,2016).

Finally, we execute two final paired moves to move the last remaining knight:

  1. (1,2017)(2,2015) and (3,2016)(2,2014);
  2. (2,2015)(3,2017) and (2,2014)(3,2016).

This concludes the proof, and the answer is that for all even k the position is impossible to reach, while for all odd k the position is possible.