Kvant Math Problem 441
Let the vertices of the convex $2n$-gon be $A_1,A_2,\dots,A_{2n}$ in cyclic order.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m50s
Source on kvant.digital
Problem
Inside a convex $2n$-gon, an arbitrary point $P$ is chosen. Through each vertex and the point $P$, a straight line is drawn. Prove that there exists a side of the polygon such that none of the drawn lines has any points in common with it (except, possibly, the endpoints of the side).
G. A. Gurevich
Exploration
Let the vertices of the convex $2n$-gon be $A_1,A_2,\dots,A_{2n}$ in cyclic order. Through each vertex $A_i$ and the interior point $P$, draw the line $PA_i$.
A side $A_iA_{i+1}$ is forbidden if some line $PA_j$ meets the interior of that side. Since the side already contains its endpoints, the only relevant intersections are with the relative interior of the side.
It is useful to understand which sides can be hit by a fixed line $PA_j$. Because the polygon is convex and $P$ lies inside it, the ray from $P$ through $A_j$ continues beyond $A_j$ and leaves the polygon through exactly one side. That side cannot be adjacent to $A_j$, since after passing through the vertex $A_j$ the line is immediately outside the polygon near that vertex. Hence each vertex $A_j$ determines at most one side, not adjacent to $A_j$, whose interior is intersected by the line $PA_j$.
For a quadrilateral, each vertex line can hit only the opposite side. There are four vertices and four sides. The opposite-side relation pairs the sides, so at most two sides are hit. Thus at least two sides remain untouched. This suggests a counting argument.
The crucial point is to show that two adjacent vertices cannot determine the same hit side. If $PA_i$ and $PA_{i+1}$ both met the interior of one side $A_kA_{k+1}$, then the two rays from $P$ through consecutive vertices would leave the polygon through the same side. Geometrically, the sector between the rays $PA_i$ and $PA_{i+1}$ contains no other vertex. In a convex polygon, the boundary arc from $A_i$ to $A_{i+1}$ consists only of the side $A_iA_{i+1}$, so a side lying elsewhere on the boundary cannot belong simultaneously to both corresponding visibility regions. This is the point that requires a careful proof.
If each side can be hit by at most two vertex lines, and consecutive vertices never hit the same side, then the vertices hitting a given side form an independent set in a cycle of length $2n$. Such a set has size at most $n$. Counting incidences between vertices and hit sides may then yield the result. A simpler route is to assign to each vertex the unique side hit by its line. Adjacent vertices receive different sides. Hence the image contains at least two sides, because a cycle cannot be colored with one color. Since there are only $2n$ vertices, at most $2n$ incidences occur. The desired conclusion needs a stronger estimate.
A better observation is that each side can be assigned to at most one of the two vertices adjacent to it, because a line through a vertex cannot hit an adjacent side. Thus every hit side receives preimages only from vertices among the remaining $2n-2$ vertices. The key combinatorial fact is that adjacent vertices determine different hit sides. Therefore the map from the $2n$ vertices to hit sides has fibers consisting of nonadjacent vertices. On a cycle of length $2n$, any set of pairwise nonadjacent vertices has size at most $n$. Hence each hit side has at most $n$ preimages. Since there are $2n$ vertices, the number of hit sides is at most $2$. This is not enough.
A different viewpoint works better. Let $s_i$ be the side through which the ray beyond $A_i$ exits the polygon. As $i$ runs cyclically, $s_i$ moves monotonically along the boundary. Consecutive values are equal or adjacent in this order. Since $s_i$ is never adjacent to $A_i$, the side index is always at least one step ahead of $i$ and at most one step behind modulo $2n$. Tracking the cyclic displacement shows that the sequence cannot cover all $2n$ sides. Thus some side is missed.
The cleanest formalization is to consider the cyclic order of the rays from $P$. Because the polygon is convex and $P$ is interior, the rays $PA_i$ occur around $P$ in the same cyclic order as the vertices. The line through $P$ and $A_i$ meets the boundary at $A_i$ and at one further point $B_i$. The point $B_i$ lies on a side not adjacent to $A_i$. As $i$ increases by one, $B_i$ moves along the boundary in the same cyclic direction and never jumps backward. Hence the sides containing the $B_i$ form a nondecreasing cyclic sequence. A nondecreasing cyclic sequence of length $2n$ on a cycle of $2n$ sides cannot visit all sides, because each term avoids the side immediately preceding and immediately following the corresponding vertex. This yields at most $2n-1$ visited sides. The omitted side is the required one.
The monotonicity of the points $B_i$ is the step most likely to hide an error and must be proved carefully.
Problem Understanding
We are given a convex polygon with an even number $2n$ of vertices and an interior point $P$. For every vertex, the line through that vertex and $P$ is drawn. We must prove that at least one side of the polygon is not intersected in its interior by any of these lines.
This is a Type B problem. The statement itself is to be proved.
The core difficulty is to relate the cyclic order of the vertices to the cyclic order in which the corresponding lines leave the polygon. Convexity and the fact that $P$ lies inside the polygon imply a strong monotonicity property for the second intersection points of these lines with the boundary.
Proof Architecture
For each vertex $A_i$, let $B_i$ be the second intersection point of the line $PA_i$ with the boundary of the polygon.
The first lemma states that the points $B_1,B_2,\dots,B_{2n}$ occur on the boundary in the same cyclic order as the vertices; this follows from the preservation of cyclic order of rays through an interior point of a convex polygon.
The second lemma states that $B_i$ never lies on either side adjacent to $A_i$; after passing through the vertex $A_i$, the line immediately leaves the polygon near that vertex.
The third lemma states that not every side can contain one of the points $B_i$; if every side did, then the cyclic order from the first lemma would force side $A_{i-1}A_i$ or side $A_iA_{i+1}$ to contain $B_i$, contradicting the second lemma.
The hardest step is the first lemma, because it requires a rigorous justification that the second intersection points inherit the cyclic order of the rays.
Solution
Let the vertices of the convex $2n$-gon be
$$A_1,A_2,\dots,A_{2n}$$
in cyclic order, with indices taken modulo $2n$.
For each $i$, consider the line $PA_i$. Since $P$ lies in the interior of the convex polygon, this line meets the boundary of the polygon at exactly two points. One of them is the vertex $A_i$. Let $B_i$ denote the other intersection point.
The point $B_i$ belongs to the interior of some side of the polygon, or coincides with a vertex. In either case, the line $PA_i$ meets exactly the side containing $B_i$ in a point other than an endpoint.
We first determine the cyclic order of the points $B_i$.
Since the polygon is convex and $P$ is interior, the rays
$$PA_1,PA_2,\dots,PA_{2n}$$
appear around the point $P$ in the same cyclic order as the vertices around the polygon. Let two consecutive rays $PA_i$ and $PA_{i+1}$ be fixed. The angle between them contains no other ray $PA_j$.
Consider the cone bounded by these two rays. Its intersection with the polygon is a convex region whose boundary on the polygon consists precisely of the side $A_iA_{i+1}$. Every ray issuing from $P$ inside this cone meets the boundary of the polygon at a point of that side. Consequently, when a ray rotates continuously from $PA_i$ to $PA_{i+1}$, its second intersection point with the boundary moves continuously along the boundary from $B_i$ to $B_{i+1}$ without passing any other point $B_j$.
Applying this to every consecutive pair of rays shows that the points
$$B_1,B_2,\dots,B_{2n}$$
occur on the boundary of the polygon in the same cyclic order as their indices.
Next we show that $B_i$ cannot lie on either side adjacent to $A_i$.
Indeed, after the line $PA_i$ passes through the boundary point $A_i$, it immediately leaves the polygon, because $A_i$ is a vertex of a convex polygon. Hence the second intersection point with the boundary cannot belong to either side having $A_i$ as an endpoint. Therefore $B_i$ lies on neither side $A_{i-1}A_i$ nor side $A_iA_{i+1}$.
Assume, for contradiction, that every side of the polygon contains at least one of the points $B_i$.
There are exactly $2n$ sides and exactly $2n$ points $B_i$. Since the points $B_i$ occur on the boundary in cyclic order, each side must contain exactly one of them. Consequently, the point $B_i$ must lie on one of the two sides adjacent to the position of $A_i$ in the cyclic order of the boundary. More precisely, because the cyclic orders of the sequences $(A_i)$ and $(B_i)$ are identical and every side contains exactly one point $B_i$, the point $B_i$ must lie either on the side $A_{i-1}A_i$ or on the side $A_iA_{i+1}$.
This contradicts the previous paragraph, which showed that $B_i$ lies on neither adjacent side.
Hence not every side contains a point $B_i$. Let $S$ be a side containing no point $B_i$.
If some line $PA_j$ met the interior of $S$, then its second intersection point with the boundary would belong to $S$, which would mean $B_j\in S$. This is impossible by the choice of $S$.
Therefore no drawn line has any point in common with the interior of the side $S$. Only the endpoints of $S$ may belong to some of the lines.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the preservation of cyclic order. A careless argument might assert that the order is obvious from a picture. The rigorous reason is that the rays from an interior point of a convex polygon meet the boundary in exactly one point in each direction, and between two consecutive rays $PA_i$ and $PA_{i+1}$ every intermediate ray reaches the boundary on the boundary arc corresponding to the side $A_iA_{i+1}$. Thus the second intersection points cannot overtake one another along the boundary.
The second delicate step is the claim that $B_i$ cannot lie on a side adjacent to $A_i$. If one forgets that $A_i$ is already a boundary point of the line, one might incorrectly allow the second intersection point to occur on an adjacent side. The line reaches the boundary at $A_i$ and immediately exits the polygon beyond that vertex, so no further boundary point can lie on either side incident with $A_i$.
The third delicate step is the contradiction obtained from assuming that every side contains some $B_i$. Since there are exactly as many sides as points $B_i$, and the cyclic orders agree, each side would contain exactly one point $B_i$. The $i$th point in the cyclic order must then lie on one of the two sides adjacent to the $i$th vertex position along the boundary. This is precisely what the previous step forbids.
Alternative Approaches
A different proof can be formulated in terms of the lines through $P$. Each line $PA_i$ determines the side through which the ray beyond $A_i$ leaves the polygon. As the vertex $A_i$ moves around the polygon, these exit sides move monotonically around the boundary. One then studies the resulting cyclic sequence of sides and shows that a side adjacent to the transition between the first and last exit side cannot occur in the sequence. This yields an omitted side directly.
The approach using the second boundary points $B_i$ is preferable because it converts the geometric statement into a statement about two cyclic orders on the boundary. Once the order preservation is established, the contradiction with the adjacent sides is immediate and requires no further combinatorial analysis.