Return to Answer

This very problem was proposed to St. Petersburg olympiad (selection round) in 2007 by Konstantin Kokhas (problem 6 for 10-th grade in the linked pdf). In the same year it was proposed - independently, I guess, - to the journal Matematicheskoe Prosveschenie (problem 5 in the linked pdf) by Maxim Kontsevich himself.

Here is a solution which is hopefully self-contained and complete.

Assume the contrary. At first, we slightly enlarge the segments so that new segments still do not overlap. After that each segment $AB$ between our $n+2$ points intersects one of $n$ segments in an interior point. This property is preserved under small perturbation of the $n$ segments. Such perturbation allows to get $n$ segments such that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line (for example, you may choose new endpoints one by one so that each time you fix an endpoint it does not lie on a line between two already fixed endpoints; and each time you fix both endpoints of a segment, the line containing it does not pass through a common point of other two lines. This is clearly possible, since already finitely many lines are forbidden and a small disc is allowed.)

Now we enlarge the segments one by one, each time either to infinity or to the intersection with another segment. We get a plane partitioned onto several convex regions. Let's prove that there are exactly $n+1$ regions and they are convex. Draw a large square and remove the parts of rays outside the circle. Then we get a planar graph with all degrees equal to 3, and the number of vertices equals $2n$ (2 vertices at endpoints of each of extended segments). Each region is a convex polygon (since going along the boundary of each of the regions we see that all angles are less than $\pi$). Thus the number of edges equals $3n$, and the number of faces equals $n+2$ by Euler formula. One face is external, so $n+1$ inner faces as desired.

This very problem was proposed to St. Petersburg olympiad (selection round) in 2007 by Konstantin Kokhas (problem 6 for 10-th grade in the linked pdf). In the same year it was proposed - independently, I guess, - to the journal Matematicheskoe Prosveschenie (problem 5 in the linked pdf) by Maxim Kontsevich himself.

Here is a solution which is hopefully self-contained and complete.

Assume the contrary. At first, we slightly enlarge the segments so that new segments still do not overlap. After that each segment $AB$ between our $n+2$ points intersects one of $n$ segments in an interior point. This property is preserved under small perturbation of the $n$ segments. Such perturbation allows to get $n$ segments such that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line (for example, you may choose new endpoints one by one so that each time you fix an endpoint it does not lie on a line between two already fixed endpoints; and each time you fix both endpoints of a segment, the line containing it does not pass through a common point of other two lines. This is clearly possible, since already finitely many lines are forbidden and a small disc is allowed.)

Now we enlarge the segments one by one, each time either to infinity or to the intersection with another segment. We get a plane partitioned onto several convex regions. Let's prove that there are exactly $n+1$ regions and they are convex. Draw a large square and remove the parts of rays outside the square. Then we get a planar graph with all degrees equal to 3, and the number of vertices equals $2n$ (2 vertices at endpoints of each of extended segments). Each region is a convex polygon (since going along the boundary of each of the regions we see that all angles are less than $\pi$). Thus the number of edges equals $3n$, and the number of faces equals $n+2$ by Euler formula. One face is external, so $n+1$ inner faces as desired.

This very problem was proposed to St. Petersburg olympiad (selection round) in 2007 by Konstantin Kokhas (problem 6 for 10-th grade in the linked pdf). In the same year it was proposed - independently, I guess, - to the journal Matematicheskoe Prosveschenie (problem 5 in the linked pdf) by Maxim Kontsevich himself.

Here is a solution which is hopefully self-contained and complete.

Assume the contrary. At first, we slightly enlarge the segments so that new segments still do not overlap. After that each segment $AB$ between our $n+2$ points intersects one of old segments in an interior point. This property is preserved under small perturbation of the $n$ segments. Such perturbation allows to get $n$ segments such that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line.

Now we enlarge the segments one by one, each time either to infinity or to the intersection with another segment. We get a plane partitioned onto several convex regions. Let's prove that there are exactly $n+1$ regions and they are convex. Draw a large square and remove the parts of rays outside the circle. Then we get a planar graph with all degrees equal to 3, and the number of vertices equals $2n$ (2 vertices at endpoints of each of extended segments). Each region is a convex polygon (since going along the boundary of each of the regions we see that all angles are less than $\pi$). Thus the number of edges equals $3n$, and the number of faces equals $n+2$ by Euler formula. One face is external, so $n+1$ inner faces as desired.

This very problem was proposed to St. Petersburg olympiad (selection round) in 2007 by Konstantin Kokhas (problem 6 for 10-th grade in the linked pdf). In the same year it was proposed - independently, I guess, - to the journal Matematicheskoe Prosveschenie (problem 5 in the linked pdf) by Maxim Kontsevich himself.

Here is a solution which is hopefully self-contained and complete.

Assume the contrary. At first, we slightly enlarge the segments so that new segments still do not overlap. After that each segment $AB$ between our $n+2$ points intersects one of $n$ segments in an interior point. This property is preserved under small perturbation of the $n$ segments. Such perturbation allows to get $n$ segments such that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line (for example, you may choose new endpoints one by one so that each time you fix an endpoint it does not lie on a line between two already fixed endpoints; and each time you fix both endpoints of a segment, the line containing it does not pass through a common point of other two lines. This is clearly possible, since already finitely many lines are forbidden and a small disc is allowed.)

Now we enlarge the segments one by one, each time either to infinity or to the intersection with another segment. We get a plane partitioned onto several convex regions. Let's prove that there are exactly $n+1$ regions and they are convex. Draw a large square and remove the parts of rays outside the circle. Then we get a planar graph with all degrees equal to 3, and the number of vertices equals $2n$ (2 vertices at endpoints of each of extended segments). Each region is a convex polygon (since going along the boundary of each of the regions we see that all angles are less than $\pi$). Thus the number of edges equals $3n$, and the number of faces equals $n+2$ by Euler formula. One face is external, so $n+1$ inner faces as desired.

This very problem was proposed to St. Petersburg olympiad (selection round) in 2007 by Konstantin Kokhas (problem 6 for 10-th grade in the linked pdf). In the same year it was proposed - independently, I guess, - to the journal Matematicheskoe Prosveschenie (problem 5 in the linked pdf) by Maxim Kontsevich himself.

Here is a solution which is hopefully self-contained and complete.

Assume the contrary. At first, we slightly enlarge the segments so that new segments still do not overlap. After that each segment $AB$ between our $n+2$ points intersects one of old segments in an interior point. This property is preserved under small moving the $n$ segments. This allows to suppose that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line.

Now we enlarge the segments one by one, each time either to infinity or to the intersection with another segment. We get a plane partitioned onto several convex regions (why convex? Because an angle greater than $\pi$ can not appear.) Let's prove that there are exactly $n+1$ regions. Draw a large circle and remove the parts of rays outside the circle. Then we get a planar graph with all degrees equal to 3, and the number of vertices equals $2n$ (2 vertices at endpoints of each of extended segments). Thus the number of edges equals $3n$, and the number of faces equals $n+2$ by Euler formula. One face is external, so $n+1$ inner faces as desired.

This very problem was proposed to St. Petersburg olympiad (selection round) in 2007 by Konstantin Kokhas (problem 6 for 10-th grade in the linked pdf). In the same year it was proposed - independently, I guess, - to the journal Matematicheskoe Prosveschenie (problem 5 in the linked pdf) by Maxim Kontsevich himself.

Here is a solution which is hopefully self-contained and complete.

Assume the contrary. At first, we slightly enlarge the segments so that new segments still do not overlap. After that each segment $AB$ between our $n+2$ points intersects one of old segments in an interior point. This property is preserved under small perturbation of the $n$ segments. Such perturbation allows to get $n$ segments such that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line.

Now we enlarge the segments one by one, each time either to infinity or to the intersection with another segment. We get a plane partitioned onto several convex regions. Let's prove that there are exactly $n+1$ regions and they are convex. Draw a large square and remove the parts of rays outside the circle. Then we get a planar graph with all degrees equal to 3, and the number of vertices equals $2n$ (2 vertices at endpoints of each of extended segments). Each region is a convex polygon (since going along the boundary of each of the regions we see that all angles are less than $\pi$). Thus the number of edges equals $3n$, and the number of faces equals $n+2$ by Euler formula. One face is external, so $n+1$ inner faces as desired.