Shapavaooov A.B.

a) On each of the fields of the top and bottom horizontal rows of an $8 \times 8$ chessboard, there is a token: white ones at the bottom, black ones at the top. In one move, it is allowed to move any token to an adjacent free cell vertically or horizontally. What is the minimum number of moves required to achieve a configuration where all black tokens are at the bottom and all white tokens are at the top?

b) The same question for a $7 \times 7$ board.
a) Evaluation. To reach the opposite side of the board, a piece needs to make seven vertical moves. However, at least one of the two pieces standing on the same vertical must make a horizontal move (otherwise, they would not be able to pass each other). Therefore, together these pieces will make no fewer than 15 moves. There are eight such pairs on the board. Thus, it is impossible to achieve the required arrangement in fewer than 120 moves.

Example. We will divide the pieces into fours, standing on two adjacent verticals. We will move each quartet in 30 moves as shown in the figure:

![](https://cdn.mathpix.com/cropped/2024_05_06_0ff1ee02df212bd75258g-02.jpg?height=549&width=1014&top_left_y=1781&top_left_x=522)

"Losses" on horizontal moves occur only on the second and fourth stages.

b) Example. We will show how to achieve the required arrangement in 92 moves, making \(14 \cdot 6 = 84\) vertical moves and 8 horizontal moves. On three pairs of verticals, we will swap the pieces as in part a), making 6 horizontal moves. The remaining 2 horizontal moves will be spent on the last vertical: the white piece lets the black piece pass halfway and then returns to the vertical.

Evaluation. From the solution in part a), it is clear that at least \((2 \cdot 6 + 1) \cdot 7 = 91\) moves are needed. That this is not enough can be shown in different ways.

First method. If 91 moves were enough, then on each vertical, exactly one piece would remain, and the other would move to an adjacent vertical, thus changing the parity of the vertical. In this case, on three even-numbered verticals, three pieces should remain, and four more pieces should move from even-numbered verticals to these, totaling 7 pieces.

Contradiction.

Second method. After each move, the number of pieces on white squares changes by 1, so its parity
[ Sequences (miscellaneous). ]
Problem