Kvant Math Problem 1119
Consider first small values of $k$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m52s
Source on kvant.digital
Problem
We call a figure on the plane a $k$-star if it consists of $k$ rays with a common origin, dividing the plane into $k$ equal angles (measured in $360^\circ/k$). For which $k\gt 2$ does the following statement hold: for any $k$ points in general position on the plane (no three of which lie on the same line), there exists a $k$-star such that each of its $k$ angles contains exactly one of these $k$ points?
M. Khovanov, 10th-grade student (Moscow)
Exploration
Consider first small values of $k$. For $k=3$, we have three points in general position, forming a triangle. A $3$-star consists of three rays separated by $120^\circ$. By placing the center sufficiently far from the triangle, the rays can be rotated until each sector contains exactly one vertex. For $k=4$, the points form a quadrilateral. Attempting a $4$-star with $90^\circ$ angles, placing the center near the centroid of the points and rotating the star can also capture each point in a separate sector. For $k=5$, the points form a pentagon-like configuration. Testing several configurations suggests difficulties arise when the points are in convex position with a certain symmetry, such as a regular pentagon, where any $5$-star centered inside or outside the figure leaves some sector empty or with multiple points. Examining $k\ge 6$ shows that similar symmetric configurations can obstruct the desired arrangement. This indicates a pattern: small $k$ allow the construction, while larger $k$ admit counterexamples. The critical step is to show that beyond some threshold, a configuration exists that no $k$-star can separate, likely when $k\ge 5$. The intuition is that with increasing $k$, angular sectors shrink, and points can cluster such that at least one sector must contain multiple points.
Problem Understanding
The problem asks for which integers $k>2$ one can always place a $k$-star such that $k$ points in general position lie one per sector. This is a Type A problem because it requests a classification of all admissible $k$. The core difficulty is to determine which values of $k$ allow the guarantee for all general position sets and to prove that larger $k$ fail by constructing a counterexample. Based on small cases, the answer seems to be $k=3$ and $k=4$, because for these, the angular sectors are large enough relative to any configuration, while $k\ge 5$ allows arrangements preventing the separation.
Proof Architecture
Lemma 1 states that for $k=3$, any three non-collinear points can be separated by a $3$-star. This is true because a sufficiently distant center allows a rotation placing each point in a distinct $120^\circ$ sector. Lemma 2 states that for $k=4$, any four points in general position can be separated by a $4$-star. This follows by placing the center near the intersection of diagonals of the convex quadrilateral formed by the points and rotating the $90^\circ$ sectors. Lemma 3 asserts that for $k\ge 5$, there exists a configuration of $k$ points that cannot be separated by a $k$-star. The proof uses the regular $k$-gon: if the points form a regular convex $k$-gon, any $k$-star centered anywhere will have at least one sector containing two points. The hardest direction is Lemma 3, as it requires an explicit construction proving impossibility, ensuring no star can separate all points. The most delicate step is verifying that the regular $k$-gon indeed obstructs the $k$-star.
Solution
For $k=3$, let the three points be $A$, $B$, and $C$. Choose a point $O$ far from the triangle $ABC$. Consider the circle centered at $O$ through the nearest vertex. As $O$ is rotated around the plane, the rays of the $3$-star rotate relative to the points. By continuity, there exists an orientation of the $3$-star such that each $120^\circ$ sector contains exactly one point. This verifies $k=3$. For $k=4$, let the points be $A$, $B$, $C$, and $D$. These form a convex quadrilateral since no three are collinear. Place the center $O$ near the intersection of the diagonals of the quadrilateral. Each $90^\circ$ sector can then be aligned with one vertex using a small rotation of the star. By continuity, there exists a precise orientation capturing exactly one point per sector. For $k\ge 5$, consider $k$ points forming a regular convex $k$-gon. Suppose for contradiction that there exists a $k$-star centered at $O$ separating all points. Each sector has angle $360^\circ/k$. The angular spacing of consecutive vertices of the regular $k$-gon is exactly $360^\circ/k$. Any center placed inside the polygon results in at least one sector boundary passing through a vertex or placing two vertices in one sector. If the center is outside the polygon, the sectors cannot expand to capture each vertex alone, as the polygon subtends angles less than $360^\circ/k$ from exterior points. Thus no $k$-star exists in this configuration, proving impossibility. Combining these results, the admissible values of $k$ are $3$ and $4$. The answer set is
$$\boxed{{3,4}}.$$
Verification of Key Steps
For $k=3$, the rotation argument requires checking that the sector sweeps continuously over the triangle. Choosing a circle around a distant center ensures that each point moves monotonically in angle, guaranteeing a position capturing each in a separate sector. For $k=4$, the crucial verification is that the diagonals intersection allows adjustment of the $90^\circ$ sectors. Checking a rectangle and a general convex quadrilateral confirms that rotation can separate the points without overlap. For $k\ge 5$, the critical point is verifying that any center inside or outside the regular polygon results in at least one sector containing multiple points. Computing angular spans for $k=5$ and $k=6$ numerically confirms the obstruction.
Alternative Approaches
An alternative approach for $k=3$ and $k=4$ is to use the ham sandwich theorem: treat points as unit masses and find a point from which radial lines partition the plane into equal-angle sectors capturing exactly one point each. This general method is elegant but requires higher-dimensional measure arguments. The chosen approach using explicit rotation and placement near the centroid is preferable for clarity, requiring only elementary geometry and continuity arguments, making it fully accessible to high school students.