$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
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$.
2. Find the configuration with the least circles that requires $ 4$ colors.
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 .