You are given $2024$ yellow and $2024$ blue points on the plane, and no three of the points are on the same line. We call a pair of nonnegative integers $(a, b)$ good if there exists a half-plane with exactly $a$ yellow and $b$ blue points. Find the smallest possible number of good pairs. The points that lie on the line that is the boundary of the half-plane are considered to be outside the half-plane. Proposed by Anton Trygub
Problem
Source: Ukrainian Mathematical Olympiad 2024. Day 2, Problem 11.7
Tags: combinatorial geometry, combinatorics
13.08.2024 22:59
The answer is $2024 \cdot 3 + 1 = \boxed{6073}$. There are exactly $6073$ good pairs if we select the points to be equally spaced on a circle, alternating in color – then, the only good pairs here are ones with $a = b$ or $|a-b| = 1$, which gives us a total of $2025 + 2024 \cdot 2 = 6073$ good pairs. To find $6073$ good pairs in any configuration of points: choose a "pivot" $P_0$ on the convex hull of the $4048$ points, and WLOG assume that $P_0$ is blue. Label the other $4047$ points $P_1$ thru $P_{4047}$ in clockwise order WRT $P_0$. To get $4048$ good pairs, draw a half-plane whose boundary passes through $P_0$ which contains $0$ points. Now, rotate the half-plane clockwise half a revolution about $P_0$ – when we are finished, it will contain every point except $P_0$. Since no three points are collinear, we must have had every amount of points from $0$ to $4047$ during the rotation, giving us our first $4048$ good pairs. We can find $2024$ more good pairs as follows: consider each of the $2024$ moments during the rotation of the half plane when the boundary of the half plane contains a yellow point $P_i$ as well as $P_0$ (which, recall, we WLOGed as blue). Suppose there are $k$ points inside the half plane right now, which does not include $P_i$ or $P_0$. If we rotate the half-plane slightly clockwise about $P_0$, we will add $P_i$ point to the half-plane, resulting in a good pair with $k+1$ points that we have already counted; however, if we rotate the half-plane slightly counterclockwise about $P_i$, we will add $P_0$ to the half-plane, resulting in a new good pair of $k+1$ points. Lastly, we have not counted the good pair $(2024,2024)$ yet; in total, we now have $6073$ good pairs, as desired.