There are $n > 1$ distinct points marked in the plane. Prove that there exists a set of circles $\mathcal C$ such that ___$\bullet$ Each circle in $\mathcal C$ has unit radius. ___$\bullet$ Every marked point lies in the (strict) interior of some circle in $\mathcal C$. ___$\bullet$ There are less than $0.3n$ pairs of circles in $\mathcal C$ that intersect in exactly $2$ points. Note: Weaker results with $\it{0.3n}$ replaced by $\it{cn}$ may be awarded points depending on the value of the constant $\it{c > 0.3}$. Proposed by Siddharth Choppara, Archit Manas, Ananda Bhaduri, Manu Param
Problem
Source: LMAO 2024 P6
Tags: combinatorics, geometry, lmao, combinatorial geometry
L567
01.06.2024 22:10
Supposedly one of the proposers also managed to do $c = 0.28$
Siddharth03
01.06.2024 22:14
L567 wrote: Supposedly one of the proposers also managed to do $c = 0.28$ That is true, $0.3$ was just to simplify the calculations for people in the contest. I would be pretty surprised if someone comes up with something that is between $0.28$ and $0.3$.
R8kt
02.06.2024 00:27
Pretty sure the constant was achieved by 3 * (1 - pi*sqrt(3)/6)
Asynchrone
02.06.2024 00:29
A question : I've never heard of the LMAO contest before, where is it run ?
AshAuktober
02.06.2024 07:55
@above LMAO is essentially the India version of ELMO, in which the Senior students of camp set a paper for the Juniors.
mathhotspot
02.06.2024 10:36
what about the possibility of doing random shifts and employing probabilistic arguments?@siddharth03
aleksijt
02.06.2024 12:09
Discarding the unpaired circles below doesn't work immediately. If I fix this, I'll edit the solution.
Take a sphere packing in $\mathbb{R}^2$ with at least $\lambda=\frac{\pi}{2\sqrt{3}}n$ points inside. As $3(1-\lambda)<0.28$, we can allow three intersections per unoccupied point.
Call the regions not occupied (bounded by three circles) in the packing that have at least $1$ point holes. The idea is that we can match holes in one direction (out of $3$) and place one circle to cover them both, intersecting exactly $4$ of the packing's circles (the new circles are passing through $4$ tangency points of the packing).
Let $a_i$ be the number of holes that have a pair in the first direction and $b_i$ be the number of holes that don't have a pair in the $i-$th direction (for $i=1,2,3$). Also, we discard all holes that don't have a pair at all (as we place a circle at each center of those holes and these don't intersect with anything else we'll place so they just use up $3$ intersections). Let $m$ be the number of holes that remain.
Claim: $2a_k\ge b_k$ for some $k=1,2,3$.
Proof. Suppose otherwise. Then \[b_1+b_2+b_3>2(a_1+a_2+a_3)\]but note $b_1+b_2+b_3\le 2m$ as we each hole is disconnected from at most $2$ holes. Similarly, $a_1+a_2+a_3\ge m$ as each hole is connected to at least one hole, a contradiction.
Now, we place one circle for each pair (in direction $k$) and place one for each non-paired point (so it's as if it were paired) such that we get exactly $4$ intersections each time (note these circles won't intersect with each other). Thus, we use \[4a_k+4b_k\le 6a_k+3b_k=3(2a_k+b_k)=3m\]intersections, so we're done.
Siddharth03
07.06.2024 08:21
Bumpp
EthanWYX2009
01.07.2024 07:23
Elegant problem, and every step is natural to come up with. First with the idea of probabilistic method, we hope to find unit circles that have no intersection but covers many points. A natural way is to use the green circles below: now if we calculate the density it is $\frac{\pi}{2\sqrt 3}\approx 0.906.$ Therefore the expectation(turn angles randomly) of points inside one of the circle is $\frac{\pi}{2\sqrt 3}n.$ Now there are only at most $1-\frac{\pi}{2\sqrt 3}\approx 0.094n$ points not covered. The idea is clear now: we hope in average each point intersacts $3$ circles. Call an area enclosed by 3 green circles and with at least one point "good area", and say 2 "good area" are connected iff they have a same point inside. We only need to consider it in a connected branches. 2 "good area" can be connected in 3 different directions, so at least one of them have $1/3$ edges. We take all of them by using red circles above. 2 "good area" correspond one unit circle and they intersact exactly 4 green circles. They will not intersact other red circle with same direction. Now the rest $1/3$ points just use other directions and have $4$ intersaction in average. So add them up and we are done.$\Box$