On the board below, it is allowed to move any object from its square to any adjacent empty square above, below, to the side, or diagonally.

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-02.jpg?height=319&width=476&top_left_y=512&top_left_x=671)

a) Show how to swap the positions of all the hats with all the trophies in just five moves. Argue why it is not possible to swap them with fewer than five moves.

b) On this other board shown below, what is the minimum number of moves to swap the hats with the trophies?

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-02.jpg?height=320&width=634&top_left_y=1204&top_left_x=590)

c) And if it were a board similar to the previous ones, but with 1000 hats and 1000 trophies, what would be the minimum number of moves to swap their positions?
![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-02.jpg?height=320&width=1312&top_left_y=1725&top_left_x=252)
Solution

a) Below, we show a sequence of five moves to swap the hats with the trophies (there is another one too)!

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-18.jpg?height=571&width=1285&top_left_y=452&top_left_x=264)

The argument to show that it is not possible to swap them with fewer than 5 moves is as follows: in the first move, we need to move a trophy or a hat to the empty space above to the right. After this move, all objects will be out of their target positions. Since there are four objects, at least four moves are needed to place them in their positions. Since one move has already been made, we will have $1+4=5$ moves at a minimum to swap the hats with the trophies.

b) Below we show a sequence of seven moves to swap the hats with the trophies:
![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-18.jpg?height=764&width=1450&top_left_y=1572&top_left_x=184)

The same argument from before applies to conclude that seven is the minimum number of moves to swap the hats with the trophies. In the first move, we need to move a hat or a trophy to the empty space. At this point, all six objects will be out of their target positions. Therefore, to place them in their positions, at least six moves are needed. Thus, we will have $6+1=7$ moves at a minimum.

c) If we repeat the pattern described above, we can swap the hats and trophies with 2001 moves! The idea is as follows. We start with the configuration

| $a$ | $a$ | a | a | a |
| :--- | :--- | :--- | :--- | :--- |
| $a$ | $a$ | $a$ | $a$ | $a$ |

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-19.jpg?height=222&width=761&top_left_y=674&top_left_x=1015)

Next, with 2 moves, we reach the configuration

| a | a | a | a | a |
| :--- | :--- | :--- | :--- | :--- |
| a | d | a | d | a |

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-19.jpg?height=219&width=764&top_left_y=1059&top_left_x=1014)

And with two more moves, we reach the configuration

| a | a | a | a | a |
| :--- | :--- | :--- | :--- | :--- |
| $a$ | $a$ | $a$ | 9 | 0 |

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-19.jpg?height=228&width=769&top_left_y=1435&top_left_x=1011)

Therefore, after 1000 moves, we reach the configuration

| a | a | a | a | a |
| :--- | :--- | :--- | :--- | :--- |
|  | $a$ | a | a | a |

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-19.jpg?height=225&width=764&top_left_y=1817&top_left_x=1014)

Now let's go back with the empty space! With two more moves (after those 1000 moves), we get the configuration

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-19.jpg?height=227&width=539&top_left_y=2242&top_left_x=436)

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-19.jpg?height=224&width=767&top_left_y=2246&top_left_x=1012)

With two more moves, we get the configuration

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-20.jpg?height=238&width=1356&top_left_y=336&top_left_x=231)

Therefore, after 2000 moves (counting those 1000 previous moves), we get the configuration

|  | $a$ | $a$ | $a$ | $a$ |
| :--- | :--- | :--- | :--- | :--- |
| 1 | 0 | a | a | 0 |

![](https://cdn.mathpix.com/cropped/2024_05_01_d02c2755ad3373bde08ag-20.jpg?height=232&width=766&top_left_y=767&top_left_x=817)

And with one more move, we are done! So, we made 2001 moves. The argument to show that it is not possible to make the swap with fewer than this is the same as the previous ones.