In the game "Drag One," a checkered board and round pieces, one black and the others white, are used. A piece is placed in each square of the board, except for one that is left empty. A move consists of moving a piece from an adjacent square to the empty square. The game ends when the black piece reaches the top right corner of the board. See an example of how to finish "Drag One" in four moves on a $2 \times 2$ board.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-09.jpg?height=166&width=165&top_left_y=1850&top_left_x=640)

initial position
![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-09.jpg?height=188&width=760&top_left_y=1850&top_left_x=858)

This sequence of moves can be described by $(\uparrow, \leftarrow, \downarrow, \rightarrow)$.

a) Describe how to finish "Drag One" in six moves on the $3 \times 3$ board below.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-09.jpg?height=151&width=157&top_left_y=2243&top_left_x=1052)

b) Describe how to finish "Drag One" in ten moves on the $3 \times 3$ board below.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-09.jpg?height=148&width=157&top_left_y=2533&top_left_x=1052)

c) Show that on an $n \times n$ board, as in the figure, it is possible to finish "Drag One" in $6n-8$ moves.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-10.jpg?height=328&width=346&top_left_y=356&top_left_x=752)

Subject

## Geometry

#
Solution

a) The figure below shows that the sequence of six moves $(\downarrow, \leftarrow, \uparrow, \leftarrow, \downarrow, \rightarrow)$ ends the game from the initial position given.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-31.jpg?height=140&width=1008&top_left_y=1301&top_left_x=632)

b) The figure below shows that the sequence of four moves $(\uparrow, \leftarrow, \downarrow, \rightarrow)$ transforms the given initial position into the initial position of item a), from which it is possible to end the game in six moves.
![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-31.jpg?height=158&width=844&top_left_y=1622&top_left_x=708)

Thus, we can end the game in a total of $4+6=10$ moves.

c) The idea is to move the black piece along the diagonal of the board. This can be done one square at a time using first the moves from the example in the statement followed by the repetition of the moves from item a). Below we illustrate this procedure on a $4 \times 4$ board.

![](https://cdn.mathpix.com/cropped/2024_05_01_984603b876c0bc28095bg-31.jpg?height=225&width=1219&top_left_y=2035&top_left_x=521)

In general, on an $n \times n$ board, the black piece will need to move up $n-1$ squares along the diagonal. By the method indicated above, the first of these can be moved in 4 moves and each of the $n-2$ remaining ones in 6 moves each. Therefore, the game can be completed in $4+6(n-2)=6n-8$ moves.

## Geometry

#