Hard Combinatorical Geometric Problem on Intersecting Circles
There's a problem I've heard a few years ago, which neither I nor any of my colleagues were able to solve, and much time has passed so we do not even know its source, even trying to google it. I'd much appreciate if someone can point at a solution to this.
On a plane there are $n$ circles with the following conditions:
- All circles have the same radius
- Each circle intersects at least one other circle
- No two circles are tangent
Given the above, prove that there are at least $n$ unique intersection points.
I have only succeeded in proving that there are at least $\sqrt{2n}$ unique intersection points.
Edit: "Unique" intersection points means disregarding multiplicities.
Solution 1:
Given a circle $C$, denote by $N(C)$ the number of unique intersection points on $C$. Also, given an intersection point $p$, denote by $m(p)$ the number of circles that go through $p$.
Let $p$ be an intersection point and $C$ a circle going through $p$. Then $$m(p)\leq N(C).$$ Indeed, there is an injection from the set of circles going through $p$ other than $C$ to the set of intersection points lying on $C$ other than $p$, since every other circle going through $p$ will intersect $C$ in another point (no tangencies, and by two given points will pass only two circles).
Now consider the sum $$S=\sum_C \sum_{p\in C} \dfrac{1}{N(C)}$$
First, since $\sum_{p\in C}={N(C)}$ for every circle $C$ one obviously has $$S=\sum_C 1=n.$$
On the other hand, $$S=\sum_p \sum_{C\ \ni p} \dfrac{1}{N(C)}\leq \sum_p \sum_{C\ \ni p} \dfrac{1}{m(p)}=\sum_p 1$$ and the last right-hand side is the number of intersection points, which concludes the proof.