Maths Olympiad Prep

Library / /67 of 87

Combinatorics Difficulty 6.8 National Olympiad Prove it Russia

The chess King was placed on a cell of the board 8×88 \times 8, and then he made 6464 moves so that he visited all the cells and returned back to the initial cell. At each moment, we calculate the distance from the center of the cell occupied by the King to the center of the board. We call the move pleasant if after the move this distance became less than it was before the move. Find the greatest possible number of pleasant moves.

(By one move the chess King moves to a cell adjacent by a side or by a vertex.)

Solution

Ответ. 4444 moves.

Let us prove that there must have been at least 2020 unpleasant moves (and thus the number of pleasant moves cannot exceed 4444). Let's place numbers in the cells as shown in рис. 3; cells with the same numbers are equidistant from the center, and cells with smaller numbers are closer to the center than those with larger numbers.

Figure 1
Рис. 3

Figure 2
Рис. 4

Every move from a cell with number 11 does not decrease the distance to the center and is therefore unpleasant — there are 44 such moves. A move from a cell with number 22 can be pleasant only if it goes to a cell with number 11. But there are eight cells with number 22 and only four with number 11, so at least four moves from cells with number 22 will be unpleasant.

Now consider moves leading to the 3232 cells with numbers not less than 66. Note that these moves cannot originate from cells with numbers 11 or 22, meaning they weren't accounted for in the previous reasoning. Such a move can only be pleasant if it comes from a cell with a number not less than 77; however, there are only 2020 such cells. Therefore, among these moves, there are at least 3220=1232 - 20 = 12 unpleasant ones, bringing the total number of unpleasant moves to no fewer than 4+4+12=204 + 4 + 12 = 20.

An example of a traversal with 4444 pleasant moves is shown in рис. 4.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.