a) João arranged 13 sticks in the shape of a rectangular fence $1 \times 4$ as shown in the figure below. Each stick is the side of a $1 \times 1$ square, and inside each of these squares, he placed an ant. What is the minimum number of sticks we need to remove to ensure that all 4 ants can escape and return to their anthills?

![](https://cdn.mathpix.com/cropped/2024_05_01_10107d2fba0ec26bc845g-07.jpg?height=103&width=300&top_left_y=725&top_left_x=981)

b) João now arranged 24 sticks in the shape of a square fence $4 \times 4$ as shown in the figure below, and inside each of these squares, he placed an ant. What is the minimum number of sticks we need to remove to ensure that all 9 ants can escape and return to their anthills?

![](https://cdn.mathpix.com/cropped/2024_05_01_10107d2fba0ec26bc845g-07.jpg?height=311&width=308&top_left_y=1135&top_left_x=977)
Solution

a) It is possible to free all the ants by removing 4 matchsticks as indicated in the following figure.

![](https://cdn.mathpix.com/cropped/2024_05_01_10107d2fba0ec26bc845g-07.jpg?height=103&width=300&top_left_y=1902&top_left_x=975)

Since each matchstick is shared by at most two squares and each square must have at least one open side for the ant inside to escape, to use 3 or fewer matchsticks, we are forced to remove at least one interior matchstick that is a side of two squares. The removal of one of these interior matchsticks merges the interiors of two small squares into a larger compartment and, from a practical standpoint, transforms the problem of freeing 4 ants in a $1 \times 4$ enclosure into the problem of freeing 3 ants in a $1 \times 3$ enclosure. If it is possible to remove 3 or fewer matchsticks in the $1 \times 4$ enclosure, it should also be possible to free the ants in a $1 \times 3$ enclosure using 2 or fewer matchsticks. By the same initial argument, this forces us to remove at least one interior matchstick, and thus the problem is again transformed into freeing 2 ants in a $1 \times 2$ enclosure by removing only one matchstick. This is clearly impossible, whether by removing the single interior matchstick or a matchstick from the edge of such an enclosure. Therefore, the minimum number of matchsticks that must be removed in this case is 4.
b) It is possible to free all the ants by removing 9 matchsticks as indicated in the example on the left of the following figure.
![](https://cdn.mathpix.com/cropped/2024_05_01_10107d2fba0ec26bc845g-08.jpg?height=324&width=734&top_left_y=431&top_left_x=564)

During the successive removal of matchsticks to free the ants, let's call any moment a compartment any closed polygonal line of matchsticks that does not have another closed polygonal line of matchsticks inside it. For example, in the figure on the right above, where 6 matchsticks have been removed, we have 3 compartments indicated by three different types of fillings. Note that the removal of a matchstick reduces the number of compartments by at most one unit. Therefore, since we initially have 9 compartments and want to ensure that no ant remains trapped in any type of compartment at the end, we must remove at least 9 matchsticks.