We want to move a rook from the bottom left corner of a chessboard to the top right corner - of course, with rook moves - such that it gets closer to the goal with every move, and each move is perpendicular to the previous one. How many ways is this possible? How many of these ways involve the rook reaching the goal in 5 moves?
I. Solution. a) It is enough to determine the number of different paths leading from the starting point to the goal, which constantly approach each other, since on each path the rook can move in exactly one way: completing each step before changing direction. For example, on both paths in Figure 1, the rook reaches the goal in 5 steps, with step lengths of $2,1,2,6,3$ and $5,3,1,4,1$ squares, respectively.

![](https://cdn.mathpix.com/cropped/2024_05_02_8043402a13f37c257e57g-1.jpg?height=637&width=550&top_left_y=337&top_left_x=755)

Due to the rules, we can only arrive at the squares in the leftmost column and the bottom row of the board from their lower or left neighbors, respectively, and this is expressed by the 1s written on the corresponding squares of the chessboard in Figure 2. For the other squares, we can arrive from both the lower and left neighbors, and the number of paths leading to each square from the starting point is the sum of the number of paths leading to the two neighbors (which must be crossed first). These sums were written on the squares, row by row, moving upwards and from left to right. According to the final entry in the goal square, the number of paths - and the number of ways the rook can move - is 3432.

| 1 | 8 | 36 | 120 | 330 | 792 | 1716 | 3432 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 1 | 7 | 28 | 84 | 210 | 462 | 924 | 1716 |
| 1 | 6 | 21 | 56 | 126 | 252 | 462 | 792 |
| 1 | 5 | 15 | 35 | 70 | 126 | 210 | 330 |
| 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 |
| 1 | 3 | 6 | 10 | 5 | 21 | 28 | 36 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| $*$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

Figure 2

b) According to the two 5-step examples in Figure 1, the rook covers the 7-square width and height between the 1st and 8th rows and columns of the chessboard in 3 and 2, or 2 and 3 steps, respectively: $2+2+3=1+6=7$, and $5+1+1=3+4=7$. (The bold digits represent the horizontal steps.) Indeed, since the required 5-step number is odd, the number of steps in the two directions must be different, and due to the alternating direction of the steps, the difference can be at most 1.

First, we determine how many ways the rook can cover 7 squares in 2 or 3 steps. It is easy to see that in 2 steps, there are 6 ways, because the rook must stop in exactly one of the 2nd, 3rd, ..., 7th rows (or columns), and this row can be chosen in 6 ways. (In the examples, the 2nd row and the 4th column.)

In 3 steps, 2 different stopping points must be chosen from the 6. If we first stop in the

$$
\text { 2nd, 3rd, 4th, 5th, } 6 \text{th. }
$$

column, the second stopping point can be chosen in

$$
5,4,3,2,1
$$

ways, because this is the number of remaining columns between the 8th column and the first chosen stopping column. (The first stopping point cannot be chosen in the 7th column.) The sum of the found numbers is 15.

Based on this, the number of 5-step movement modes is $15 \cdot 6 \cdot 2=180$. Indeed, each such mode can be obtained by inserting the 2-step coverage of the height into each of the 15 possibilities of covering the width in 3 steps, at the stopping points, and finally multiplying by 2 because in each movement mode, the width and height can be swapped. In the two examples in Figure 1,