Let \( S \) be a set consisting of \( 2024 \) points on a plane, such that no three points in \( S \) are collinear. A line \( \ell \) passing through any two points in \( S \) is called a "weakly balanced line" if it satisfies the following condition: (Condition) When the line \( \ell \) divides the plane into two regions, one region contains exactly \( 1010 \) points of \( S \), and the other region contains exactly \( 1012 \) points of \( S \) (where each region contains no points lying on \( \ell \)). Let \( \omega(S) \) denote the number of weakly balanced lines among the lines passing through pairs of points in \( S \). Find the smallest possible value of \( \omega(S) \).
Problem
Source: KMO P3
Tags: combinatorics, geometric combinatorics
MathLuis
11.11.2024 05:49
Note that from the famously well-known solution to IMO 2011/2 (a.k.a. The Windmill Problem) we have that for each point on this plane, there is a line through such point and another one from $S$ such that it splits the number of points in half, we will use this to prove that $\omega(S)=2023$.
Proof of sufficiency: Construct a regular 2023-gon and it's center, now just note that from the center, all the lines to other points in $S$ split the plane in regions of equal number of points by symetry, and for any point on the regular 2023-gon it's trivial to see that there is only two lines from it connected to the points in the 2023-gon that are the most far from it in $S$, that satisfy splitting one side in $1010$ points and the other in $1012$, since each line now over all is counted twice it's trivial to deduce that there is exactly $2023$ weakly balanced lines in this set $S$.
Proof of necessity: From each point $P$ in $S$ consider the ray $\ell$ from it to a point such that it satisfies the splitting in half condition, now first rotate it clockwise, consider $\ell'$ the reflection of $P$ over $\ell$, now the process will be the following: If $\ell'$ hits a point in $S$ before $\ell$ note that the number of points on the "left-side" (or you can just color one region black and the other white to avoid confusion), is invariant, but if it $\ell$ hits yet another point before $\ell'$ does then the number of points on "left-side" decreases by $1$, and this just repeats itself until you reaches a minimun in the number of points you could have in your left side of the half plane divides by the union of $\ell$ and $\ell'$ (by continuing this way I mean that if $\ell'$ hit something before $\ell$, then you swap the process now for $\ell'$ and so on), an analogous thing holds for conter-clockwise rotation of $\ell, \ell'$ except that now left side number of points increases.
Now define $P$ to be a "center" if for every other point in $S$ the line from $P$ to any other such point, splitted the plane in two half-planes with equal number of points on each side.
Now if FTSOC there was more than one center (at most) then consider a pair of centers $P,Q$ then consider $P_1$ to be the first point hit in the process from ray $PQ$ but also $Q_1$ same thing but from ray $QP$, notice that clearly the next point hit from the P-process is $Q_1$ meanwhile next point to be hit from the Q-process has to be $P_1$ but this is clearly a contradiction, therefore at most one center exists in $S$.
Now if a point is not a center then at some point in the process creates two weakly balanced lines and if from there the number of points on the halfplanes is invariant then it makes more, so from any non-center at least two weakly balanced lines are created, therefore if you assume a center on $S$ existed then since each other weakly balanced line has been counted twice we have that there is at least $2(2024-1) \cdot 0.5=2023$ weakly balanced lines.
Thus we are done .
seoneo
14.11.2024 17:49
Let $n=1011$. Then the total number of points is $2n+2$. By considering oriented lines we can distinguish the left and right region of lines. We denote $\overrightarrow{PQ}$ as the oriented line directed from $P$ to $Q$. (Of course the notation is overloaded for the half line, we do not need the notion of half line in this solution.) On an oriented line, for two different points $A$, $B$ on it, if the orientation agrees with the direction from $B$ to $A$, we say $A$ is a front point of $B$. An oriented line through two points on $S$ is a weakly equiable line(WEL from now on) if and only if it has $n+1$ and $n-1$ points on its left and right side respectively, or vice versa. Now, when we rotate an oriented line through $P \in S$, each time the line passes a point, the number of points on the left side either increases by $1$, decreases by $1$, or remains the same. More specifically, rotating counter clockwise, if it moves from the front point (respect to $P$) to another point on the left side, the number of points on the left decreases by $1$. If it moves from the front point to another point on the right side, the number of points on the left remains the same, and so on. Let $l(\ell)$ be the number of points in $S$ on the left side of $\ell$. Now observe the following (*) If for a line rotating about $P \in S$, there is a point $Q \in S$ so that $l(\overrightarrow{PQ} \ge n+1$ or $l(\overrightarrow{PQ} \le n-1$, then there exists a WEL through $P$. To see this, suppose that for some $P, Q \in S$, $l(\overrightarrow{PQ}) \ge n+1$. If the equality holds, we are done. If the inequality is strict, noting that $l(\overrightarrow{QP} < n-1$ showing that there was a moment that the line have been WEL, since the increment of the number $l(\ell)$ is one of $1, -1, 0$. Now, a point $G \in S$ is said to be stable if there does not exists WEL through it. Step 1. There is at mose one stable point. Suppose that $G$ is stable. Then $l(\overrightarrow{GP}) = n $ for all $P \in S$ other than $G$ by (*). Now suppose that $H \neq G$ is another stable point. Considering the line $GH$, WLOG assume that rotating $\ell$ through $G$ from $\overrightarrow{GH}$, the first point of contact $P$ was a front point of $G$ on the oriented line. But then $H$ cannot be stable, an absurdity. Step 2. There are at least $2n+1$ WEL. Apart from the stable points, every point has at least two WEL through it. To verify this, let $P \in S$ be a point which is not stable and $\overrightarrow{PQ}$ is WEL and let $\ell$ be the rotating line through $\ell$. WLOG $l(\overrightarrow{PQ}) = n+1$. Since $Q$ is a front point of $P$, $l(\overrightarrow{PQ}) $ cannot increase at the vary next contact, say contact point $T$. If it remains same, we are done. Now the case $l(\overrightarrow{PT}) = n$ remained. Suppose further that there is unique WEL through $P$. Then $(\overrightarrow{\ell} = n $ at each moment of contact. So it touches the points on left and right alternatively. However, there are $n$ points on the left whereas just $n-1$ points on the right which is impossible. Hence there is at least two WEL through $P$. Step 3 There are at least $2n+1$ non stable points and for each of those points there are at least two WEL. Since WEL passes through exactly two points in $S$, there are at least $2n+1$ WEL. Step 4 The set of all vertices of a regular $2n++1$ gon with additional point at the center provides the example completing the solution. PS. Posted at https://artofproblemsolving.com/community/u281710h3443334p33202616