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
01.06.2024 22:10
Supposedly one of the proposers also managed to do $c = 0.28$
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$.
02.06.2024 00:27
Pretty sure the constant was achieved by 3 * (1 - pi*sqrt(3)/6)
02.06.2024 00:29
A question : I've never heard of the LMAO contest before, where is it run ?
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.
02.06.2024 10:36
what about the possibility of doing random shifts and employing probabilistic arguments?@siddharth03
02.06.2024 12:09
07.06.2024 08:21
Bumpp
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$