4. Dana is a triangular grid of size $9 \times 9$ (see figure). At the top node of the grid, there is an ant colony, and at the rightmost node, there is their anthill. In all other nodes of the grid, there is one grain of rice. Each ant from the colony travels along the edges of the grid, but only in the directions right, down, or diagonally down-right. On its way, each ant collects all the grains of rice it encounters, and when it reaches the anthill, it stays there. What is the minimum number of ants that must be in the colony so that all the grains of rice can be collected?

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-03.jpg?height=771&width=782&top_left_y=1219&top_left_x=1134)

## 59th Mathematical Competition for High School Students in Slovenia  Kranj, April 18, 2015

## Problems for 3rd Year

Solve the problems independently. You have 210 minutes for solving.

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-04.jpg?height=163&width=417&top_left_y=364&top_left_x=1499)
The use of notes, literature, or a pocket calculator is not allowed.
II/4. The colony must contain at least 5 ants.

First, let's prove that 4 ants cannot collect all the grains of rice. Consider the grains of rice that lie on the five marked nodes of the grid.

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-13.jpg?height=691&width=708&top_left_y=223&top_left_x=271)

Since ants can only move to the right, down, or diagonally down to the right, each ant can collect at most one of these grains of rice, so 4 ants cannot collect all of them.

Now let's prove that 5 ants can collect all the grains of rice. For example, the $i$-th of these 5 ants can first walk diagonally down to the right along the $i$-th column of the grid, then down along that column to one of the marked nodes of the grid, then along the row to the right to the edge of the grid, and finally diagonally down to the right to the anthill. The path of the third ant is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-13.jpg?height=693&width=697&top_left_y=1264&top_left_x=271)

These 5 ants indeed collect all the grains of rice, as the first ant empties the first column and the last row of the grid, the second ant empties the second column and the second-to-last row, and so on.

Conclusion that each ant can collect at most one of the grains on the marked

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-13.jpg?height=45&width=1631&top_left_y=2122&top_left_x=218)

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-13.jpg?height=52&width=1627&top_left_y=2170&top_left_x=223)

Conclusion that the colony must contain at least five ants ............................... 1 point
Unambiguous description of the path of the five ants that collect all the grains, and the conclusion that five ants $\qquad$
Justification that the ants from the upper point indeed collect all the grains ................ 1 point

If the contestant does not have a correct justification for the fact that the colony must contain at least five ants, they do not receive a point in the third line.

If the path description in the fourth line is provided with a sketch that clearly shows that all grains are collected, the contestant is also credited with the point in the last line.