4. Dana je pravokotna mreža velikosti $7 \times 9$ (glej sliko). V spodnjem levem vozlišču mreže je kolonija mravelj, v zgornjem desnem vozlišču pa je njihovo mravljišče. V vseh ostalih vozliččih mreže je po eno zrno riža. Vsaka mravlja iz kolonije se na poti do mravljišča sprehaja po povezavah mreže, vendar le v smereh desno ali navzgor. Na svoji poti pobere vsa zrna riža, na katera naleti, in ko pride do mravljišča, tam tudi ostane. Najmanj koliko mravelj bi moralo biti v koloniji, da bi lahko pobrale vsa zrna riža?

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-02.jpg?height=551&width=771&top_left_y=1301&top_left_x=1139)

9

## 59th Mathematical Competition for High School Students in Slovenia

Kranj, April 18, 2015

## Problems for 2nd Year

Solve the problems independently. You have 210 minutes to solve them.

![](https://cdn.mathpix.com/cropped/2024_06_07_77e56b77a012e45bd48fg-03.jpg?height=157&width=402&top_left_y=361&top_left_x=1501)
The use of notes, literature, or a pocket calculator is not allowed.
I/4. The colony must contain at least 8 ants.

First, let's prove that 8 ants can collect all the grains of rice. For example, the $i$-th of these 8 ants can first move vertically upwards to the $i$-th row of the grid, then move to the right along the $i$-th row to the far right edge of the grid, and finally move upwards to the anthill. In this way, these 8 ants can collect all the grains of rice, as the $i$-th ant empties the entire $i$-th row of the grid.

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

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

Since ants can only move to the right or upwards, no ant can collect two of these grains of rice. Therefore, 7 ants cannot collect all 8 of these grains of rice.

Correct answer: 8 ants

1 point

Proof that 8 ants can collect all the rice .............................................................................. Identification of key nodes ..............................................................................

Proof that 7 ants cannot collect all the grains on the marked nodes . ....... 1 point