Let $n$ be a positive integer. Bolek draws $2n$ points in the plane, no two of them defining a vertical or a horizontal line. Then Lolek draws for each of these $2n$ points two rays emanating from them, one of them vertically and the other one horizontally. Lolek wants to maximize the number of regions in which these rays divide the plane. Determine the largest number $k$ such that Lolek can obtain at least $k$ regions independent of the points chosen by Bolek.
Problem
Source: Polish MO Finals P2 2024
Tags: combinatorics, combinatorics proposed, combinatorial geometry, game
10.07.2024 19:34
I found this problem to be quite challenging, by far harder than P3 Firstly, fix the choice of Loleks rays and start adding them one by one. When we add a new ray, all it's intersections divide a region into two, so after all rays have been added the total number of regions is one more than the number of ray intersections. $2n$ of them are trivial - the original points, call others non-trivial. Our goal is to maximize the amount of non-trivial intersections. Claim 1: for any points drawn by Bolek it is possible to get $2n^2$ non-trivial intersections Proof: Find the vertical line, such that to the left of it there are $n$ points and to the right of it there are $n$ points. Same with a horizontal line. Now the plane is divided into $4$ regions, let points in the left-bottom region make lines to the right and up directions, etc. Also let $a$ be the number of points in the left-bottom and right-top regions, and $n-a$ in the left-top and right-bottom. Then pairs of points in diagonally opposite regions create $2$ intersections, and any other pair of points in different regions creates $1$, so we get at least $2a^2+2(n-a)^2+4a(n-a)=2n^2$ non-trivial intersections, just as desired Claim 2: for some configuration of points, it is not possible to get more than $2n^2$ non-trivial intersections Proof: Let the points be $x=y=a$, where $a=1,\ldots ,2n$ Divide points in pairs: $x=y=a$ is in pair with $x=y=2n+1-a$. Now let's start counting the intersections: In each pair, there are not more than $2$ intersections If we take two pairs, let the outter one be main. Take any point of the inner one. Its horizontal ray can intersect not more than one of vertical rays of the main pair, same with vertical ray, so not more than $2$ intersections. This holds for both points of the inner pair, so two pairs can create not more than $4$ intersections Summarizing everything, we get not more than $2n+4\frac{n(n-1)}{2}=2n^2$ non-trivial intersections, which is the desired Finally, we proved that $2n^2$ non-trivial intersections is the best we can achieve, and so $k=2n^2+2n+1$ Remark While solving this problem, I missed that the number of points is even, and so was solving for $m$ points. In this case the number of non-trivial intersections is $2 \lfloor \frac{m}{2} \rfloor \lceil \frac{m}{2} \rceil$, and so the answer is $k=2 \lfloor \frac{m}{2} \rfloor \lceil \frac{m}{2} \rceil + m + 1$