Berroov S.L.

A convex 2011-gon is drawn on the board. Petya sequentially draws diagonals in it such that each newly drawn diagonal intersects no more than one of the previously drawn diagonals at an internal point. What is the maximum number of diagonals Petya can draw?
We will prove that in a convex $n$-gon $A_{1} A_{2} \ldots A_{n}$, the maximum number of diagonals that can be drawn in the specified manner is $2 n-6$. Petya can sequentially draw the diagonals $A_{2} A_{4}, A_{3} A_{5}$, $A_{4} A_{6}, \ldots, A_{n-2} A_{n}$, and then the diagonals $A_{1} A_{3}, A_{1} A_{4}, A_{1} A_{5}, \ldots, A_{1} A_{n-1}$; in total, $2 n-6$ diagonals. The figure below provides an example for $n=9$.

![](https://cdn.mathpix.com/cropped/2024_05_06_e53884ac984930b8f3cbg-44.jpg?height=792&width=851&top_left_y=1348&top_left_x=615)

We will show that it is impossible to draw more diagonals.

First method. Induction on $n$. The base case ($n=3$) is trivial.

Inductive step. Suppose, for definiteness, that $A_{1} A_{k}$ is the last diagonal drawn. It intersects no more than one previously drawn diagonal (denote it by $d$ if it exists).

All diagonals, except for $A_{1} A_{k}$ and possibly $d$, were drawn either in the $k$-gon $A_{1} A_{2} \ldots A_{k}$ or in the $(n+2-k)$-gon $A_{k} A_{k+1} \ldots A_{n} A_{1}$. By the inductive hypothesis, the number of these diagonals is no more than $(2 k-6) + (2(n+2-k)-6) = 2 n-8$. Considering the diagonals $A_{1} A_{k}$ and $d$, we get that the total number of diagonals is no more than $2 n-6$.

Second method. We will color the drawn diagonals red and blue: the first diagonal will be colored blue; subsequently, if the newly drawn diagonal intersects a blue diagonal, we will color it red, otherwise, we will color it blue. Clearly, diagonals of the same color will not intersect at internal points.

Suppose there are $k$ diagonals of the same color. Since they do not have common internal points, they divide the $n$-gon into $k+1$ polygons. Each of these polygons has at least three sides, so the total number of sides $S$ is at least $3(k+1)$. On the other hand, the sides of these polygons are our diagonals (each counted twice) and the sides of the original $n$-gon. Thus, $n + 2k = S \geq 3(k+1)$, or $k \leq n-3$. Therefore, there are no more than $n-3$ diagonals of each color, and in total, no more than $2(n-3)$ diagonals.

## [ Polyhedra and Polygons (other) ] Difficulty: 4  [ Minimum or Maximum Distance (Length) $]$  Problem 116752 Topics: [ Angles between Lines and Planes ]

Authors: Bogdanov I.I., Karasev R.

Inside a convex polyhedron, a point $P$ and several lines $l_{1}, \ldots, l_{n}$ passing through $P$ and not lying in the same plane are chosen. For each face of the polyhedron, we assign the line from $l_{1}, \ldots, l_{n}$ that forms the largest angle with the plane of that face (if there are several such lines, choose any one of them). Prove that there is a face that intersects with its corresponding line.

## Solution

Consider the points of intersection $A_{1}, A_{2}, \ldots$ of the planes of the faces with their corresponding lines. Choose the smallest segment $P A_{i}$ among all such segments (if there are several, consider any one of them). Denote this segment by $P A$. Suppose that the point $A$ does not belong to its face. Then the line $P A$ intersects some other face at an internal point $C$. Consider the corresponding line $P B$ for this face (see figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_e53884ac984930b8f3cbg-45.jpg?height=809&width=784&top_left_y=996&top_left_x=657)

Since $\beta \geq \gamma$, we have $P C \geq P B$. On the other hand, $P A > P C$. Then $P A > P B$, which contradicts the choice of segment $P A$.