1
$\begingroup$

Problem:

There's $n$ red and black circles(that means, the number of the circles is $n$) on a plane, where $n$ is even. Their radius don't need to be equal, and they cannot completely overlap the other circles(they can intesect). Paint the tangent point of a red circle and a black circle blue. Prove that the maximum of blue points is $\dfrac{n^2}{4}$.

My attempt: $\dfrac{n^2}{4}$ means to hold $n/2$ red circles and $n/2$ black circles, and each circle is tangent with all other circles with the other color. However no matter how I construct, the answer always seems to be $\Theta (n)$, and I don't know how to proceed further.

Also please notice that internally tangent are also supported.

Any hint or advice is appreciated.

UPD: Sorry for my mistake. The circles can intersect with each other.

$\endgroup$
3
  • 1
    $\begingroup$ Are you sure the question does not just mean prove that the number of blue points is at most $\frac {n^2}{4}$? $\endgroup$ – S. Dolan Sep 11 '19 at 13:56
  • $\begingroup$ @S.Dolan I am sure unless I misunderstood the problem. $\endgroup$ – FFjet Sep 11 '19 at 14:03
  • $\begingroup$ I strongly suspect that the graph whose vertices are circle, joined by an edge when they are tangent, is planar. Since planar graphs with $n$ vertices have at most $3n-6$ edges, it would follow you can only get $\Theta(n)$ red/black pairs. $\endgroup$ – Mike Earnest Sep 13 '19 at 16:13
1
$\begingroup$

Let $r$ be the number of red circles. The number of black circles is then $n-r$.

Every pair of circles consisting of one red and one black circle can have at most one tangent point. The largest number of blue points is when every red circle is tangent to every black circle, and all those tangent points are distinct. The number of such red-black pairs is $r(n-r)$.

Therefore, there are never more than $r(n-r)$ blue points.

The value of $r(n-r)$ is largest when $r=\frac{n}{2}$ (you'll still have to prove this), so the number of blue points cannot exceed $\frac{n}{2}(n-\frac{n}{2})=\frac{n^2}{4}$.

Note however that $\frac{n^2}{4}$ is not attainable for every $n$, it is only an upper bound.

$\endgroup$
3
  • $\begingroup$ What's the construction for $r=n/2$? $\endgroup$ – FFjet Sep 11 '19 at 15:07
  • $\begingroup$ $\frac{n^2}{4}$ is only an upper bound. It is only attainable for small $n$, not for all $n$. $\endgroup$ – Jaap Scherphuis Sep 11 '19 at 15:10
  • $\begingroup$ @JaapScherphuis You're right, ,my solution was incorrect. $\endgroup$ – Ingix Sep 11 '19 at 15:13
1
$\begingroup$

There is a known maximum to the number of circles which can be tangent to 3 given circles. This number is 8 and involves overlapping circles..

Therefore the value of $\frac{n^2}{4}$ can only be attained for small $n$.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.