$1989$ equal circles are arbitrarily placed on the table without overlap. What is the least number of colors are needed such that all the circles can be painted with any two tangential circles colored differently.
Problem
Source: China TST 1989, problem 7
Tags: combinatorics unsolved, combinatorics
mavropnevma
14.09.2009 02:53
This is a very old problem of Paul Erdos. There are two more spin-off questions of it; 1. Same for an infinite number of equal circles in the plane; Both the finite and infinite problems have answer $ 4$.
Pick a point $ P$ in the plane, such that its distances to the centers of the circles are all distinct (there exists such a point, since the perpendicular bisectors of the segments determined by the centers are at most countable), and order the circles by the distance of their centres from $ P$. Show that there always is a fourth color available for the next ...
2. Find the configuration with the least circles that requires $ 4$ colors.
FISHMJ25
01.08.2018 19:29
Contruction for 4 colours is :https://youtu.be/-3-t9NQcevQ i think it can be found here .Next we show by induction that we need at most 4 colours .We got some contruction with n+1 circles and we know that we can colour any number of circles up to n with 4 colours.Then make coordinate system and take circle with highest y coordinate and if some of them have same y coordinates take one with lowest x coordinate.Then that circle is tangent to at most 3 circles(can be proved ) and take by inductive step we can colour all other n circles and that circle can have fourth colour .