5. Let \( n \) be an odd natural number. A square with side \( n \) is divided into \( n^2 \) unit squares. The sides of these squares determine a total of \( 2n(n+1) \) unit segments. Some of these segments are painted red, with each unit square having at least two red sides. What is the minimum number of segments that can be painted red?

## Third Grade - A Category
5. There are $n^{2}$ unit squares, each having at least two red sides, which means that there are at least $2 n^{2}$ pairs of the form

## (unit square, its red side)

However, each red segment appears in at most two such pairs, so there are at least $n^{2}$ red segments.

Assume there are exactly $n^{2}$. Then each of them lies in exactly two unit squares, and each unit square has exactly two red segments (otherwise, one of the estimates from the previous paragraph would be a strict inequality, and the number of red segments would have to be strictly greater than $n^{2}$). Color the unit squares black and white, like a chessboard. Each red segment is in exactly one white square (and one black one), and since each white square has two red sides, it follows that there are $\frac{1}{2} n^{2}$ white squares, which is not an integer; a contradiction.

Therefore, there are at least $n^{2}+1$ red segments. We will show that this value can be achieved. It is sufficient to color all horizontal segments except those on the sides of the large square, and the vertical unit segments that belong to two horizontal sides of the large square alternately (the first, third, fifth...). This way, $n(n-1)+\frac{n+1}{2}+\frac{n+1}{2}=n^{2}+1$ segments are colored, completing the proof.

## Third grade - A category