## Task 2.

On each field of an $n \times n$ board, a dragon is sleeping. Dragons are neighbors if they are on fields that share a side. Every hour, Mini wakes up one dragon that has at least one living neighbor, and Maks directs that dragon towards one of its living neighbors. The awakened dragon breathes fire and destroys the chosen neighbor, then goes back to sleep.

Mini wants to reduce the number of dragons, while Maks wants as many dragons to remain as possible. If both choose the best they can, how many dragons will remain on the board for

(a) $n=4$ ?

(b) $n=5$ ?
## Solution.

(a) Mini cannot choose which neighbor the awakened dragon will destroy, but if she selects the same dragon enough times, she can achieve that all its neighbors are destroyed. We claim that on a $4 \times 4$ board, four dragons will remain.

In the image, the positions of four dragons that are not adjacent to each other are shown, and each other dragon is adjacent to one of them. By selecting each of these dragons three times, Mini can ensure that only four dragons remain, regardless of Max's choices.

![](https://cdn.mathpix.com/cropped/2024_05_30_e0844b4ffaefcb765e92g-2.jpg?height=620&width=625&top_left_y=1226&top_left_x=721)

In the same image, four regions are marked, each containing four fields with a dragon in the center (marked dragon). Max can achieve that at least one dragon remains in each of these regions by the following strategy: if it is possible to choose the directions of the dragons so that the marked dragons are not destroyed. If this is not possible, then within some region, Mini has chosen a dragon whose only neighbor on the board is the marked dragon in that region. Thus, the marked dragon will be destroyed, but the chosen dragon will no longer have a neighbor and will not be destroyed.

(b) We claim that on a $5 \times 5$ board, six dragons will remain. Divide the board into six regions as shown in the image. Each region contains a dragon in the center and its neighbors, and there are still two free fields on the board that do not belong to any region. Max can achieve that at least six dragons remain on the board (one in each of the six regions) using a strategy analogous to the one described for the $4 \times 4$ board.

![](https://cdn.mathpix.com/cropped/2024_05_30_e0844b4ffaefcb765e92g-3.jpg?height=617&width=623&top_left_y=183&top_left_x=725)

The following sequence of choices by Mini can ensure that no more than six dragons remain on the board, regardless of Max's choices. First, Mini selects the dragon in the center of the board four times.

![](https://cdn.mathpix.com/cropped/2024_05_30_e0844b4ffaefcb765e92g-3.jpg?height=614&width=625&top_left_y=998&top_left_x=721)

Next, Mini selects a corner of the board, and Max destroys one of the two dragons that will be destroyed. Without loss of generality, we can assume that Mini selected the top right corner of the board, and Max destroyed the dragon below that field. After that, Mini selects the neighbor that is not destroyed (to the left of the corner field) three times.

![](https://cdn.mathpix.com/cropped/2024_05_30_e0844b4ffaefcb765e92g-3.jpg?height=617&width=623&top_left_y=1913&top_left_x=722)

In the next move, Mini selects the dragon in the top left corner, and one of its two neighbors is destroyed. In the image, it is assumed that Max chose the neighbor below the corner field. By selecting the other neighbor twice, Mini ensures that there is exactly one dragon in the shaded square.

![](https://cdn.mathpix.com/cropped/2024_05_30_e0844b4ffaefcb765e92g-4.jpg?height=611&width=625&top_left_y=434&top_left_x=721)

Finally, Mini divides the remaining part of the board into three regions, two of which have four fields and one has three fields, and selects the central dragon in each of these regions until exactly six dragons remain on the board.

![](https://cdn.mathpix.com/cropped/2024_05_30_e0844b4ffaefcb765e92g-4.jpg?height=619&width=623&top_left_y=1301&top_left_x=725)