7. In each cell of a $10 \times 10$ board, there sits a rabbit. Between rabbits in adjacent cells, there are partitions that can be removed. What is the minimum number of partitions that need to be removed so that any rabbit can visit any other rabbit, traveling through no more than 17 cells (not counting the starting and ending cells)?
Solution. An example for 100 partitions is given in the figure. The correctness of the example follows from the fact that, as can be easily seen, any rabbit can reach the central 4-cell square by moving no more than 8 cells. From the central square to any cell, it can also be reached in no more than 8 moves. No more than 2 moves are required for movement within the central square. In total, $8+2+8=18$ cells, counting the final one.

We will show that fewer than 100 partitions cannot be removed. Consider

![](https://cdn.mathpix.com/cropped/2024_05_06_5ae069f21c324d13d367g-2.jpg?height=499&width=503&top_left_y=984&top_left_x=1462)
a graph where the vertices are cells and the edges are the missing partitions. Since the graph is connected, it has at least 99 edges, and we only need to show that exactly 99 cannot be. Suppose this is the case. Then the graph is a tree. Let's mentally divide the board into two halves: the upper and the lower. Then there must be a path from A1 to K1 (i.e., from the lower left to the lower right corner) that lies in the lower half - if it rises to the upper half, it will be longer than the required 18 edges. Similarly, the path from A10 to K10 must lie only in the upper half, the path from A1 to A10 only in the left half, and the path from K1 to K10 only in the right half. By combining these paths and shortening the edges traversed in both directions, we will obtain a non-trivial cycle (we go from the lower left quarter to the upper left, then from there to the upper right, then to the lower right, and back), which cannot exist in a tree.

Criteria for determining winners and prizewinners of the final stage of the Youth Mathematical School Olympiad, 2015-16.

Each problem is worth 1 point.

For 4th grade:

A winner is a participant who solves 6 problems.

A prizewinner is a participant who solves at least 4 problems.

For 5th grade:

A winner is a participant who solves at least 6 problems.

A prizewinner is a participant who solves at least 4 problems.

For 6th grade:

A winner is a participant who solves 7 problems.

A prizewinner is a participant who solves at least 5 problems.

For 7th grade:

A winner is a participant who solves 7 problems.

A prizewinner is a participant who solves at least 5 problems.

For 8th grade:

A winner is a participant who solves 6 problems.

A prizewinner is a participant who solves at least 4 problems.

For 9th grade:

A winner is a participant who solves 8 problems.

A prizewinner is a participant who solves at least 6 problems.

For 10th grade:

A winner is a participant who solves 9 problems.

A prizewinner is a participant who solves at least 5 problems.

For 11th grade:

A winner is a participant who solves 7 problems.

A prizewinner is a participant who solves at least 5 problems.