7.6. In each cell of a $5 \times 5$ square, exactly one diagonal has been drawn. A vertex of a cell is free if it is not the endpoint of any of the drawn diagonals. Find the maximum possible number of free vertices.
Answer: 18 vertices.

Solution. Example. See Fig. 7.6a. On each of the six horizontal lines, three vertices are free.

Estimate. The total number of cell vertices: $6 \cdot 6=36$. Let's select nine cells that do not share any vertices (see Fig. 7.6b). They contain all 36 vertices. In each cell, a diagonal is drawn, so in each cell, two
![](https://cdn.mathpix.com/cropped/2024_05_06_1352dda72600d03d8cc2g-2.jpg?height=412&width=840&top_left_y=2344&top_left_x=1074)

Fig. 7.6b
vertices are not free. Therefore, at least 18 vertices are used, so no more than $36-18=18$ can be free.

Grading Criteria.

“+” A complete and justified solution is provided

“Ғ” The correct answer and a correct example are provided, but the estimate is not made

“干” The correct answer is provided and the estimate is proven, but the example is missing or incorrect

“-” Only the answer is provided

“-” The problem is not solved or is solved incorrectly