For every point on the plane, one of $ n$ colors are colored to it such that: $ (1)$ Every color is used infinitely many times. $ (2)$ There exists one line such that all points on this lines are colored exactly by one of two colors. Find the least value of $ n$ such that there exist four concyclic points with pairwise distinct colors.
Problem
Source: Chinese Northern Mathematical Olympiad 2007
Tags: combinatorics proposed, combinatorics
05.12.2007 17:48
the second condition is not very clear... ¿each point have a monochromatic line, a bichromatic or there is only one of such lines?
07.08.2021 18:32
Obviously, $n \ge 4$. If $n = 4$, let the colors be labeled $1, 2, 3, 4$. Take a certain circle $\Gamma$ and take three points $A, B, C$ on $\Gamma$. Let all points on arc $AB$ (including $A$ but not $B$) be colored $1$, all points on arc $BC$ (including $B$ does not contain $C$) be colored $2$, all points on arc $CA$ (including $C$ but does not contain $A$) be colored $3$, and all other points on the plane be colored $4$. Then both conditions are satisfied, but the only circle containing points with colors $1, 2, 3$ doesn't contain a point with color $4$. Thus, $n \neq 4$, so $n \ge 5$. If $n = 5$, let the colors be labeled $1, 2, 3, 4, 5$. From condition (2), there exists a line $\ell$ such that all points on it are of only two colors. Let us suppose that there are only points with colors $1, 2$ on line $\ell$, and from condition (1), there exist points $A, B, C \notin \ell$ with colors $3, 4, 5$ respectively. If $A,B,C$ are not collinear, let $\Gamma$ be the circle passing through points $A, B, C$. If $\Gamma$ has a common point with $\ell$, then there are $4$ concyclic points of different colors, and we are done. If $\Gamma$ and $\ell$ do not intersect, but there is a point colored $1$ or $2$ on $\Gamma$, then there are $4$ concyclic points of different colors, and we are done. If $\Gamma$ and $\ell$ do not intersect, and there are no points with colors $1$ or $2$ on $\Gamma$, i.e. all points on $\Gamma$ are colored $3, 4$ or $5$, then let $O$ be the center of $\Gamma$. Let $D$ be the point on $\ell$ such that $OD \perp \ell$. WLOG assume $D$ has color $1$. Let $E$ be a point on $\ell$ with color $2$. Let line $OD$ intersect $\Gamma$ at $P$ and $Q$, where $P$ is closer to $\ell$ than $Q$. Then let $QE$ intersect $\Gamma$ at $R$. WLOG assume $P$ has color $3$. If $R$ is not colored $3$ then since $\angle ERP = \angle EDP = 90^{\circ}$, $E,R,P,D$ are concyclic and we are done. So assume $R$ has color $3$. Now let $QB$ intersect $\ell$ at $F$. Note that $B$ has color $4$. If $F$ has color $2$ then since $\angle PBF = \angle PDF = 90^{\circ}$, $P,B,F,D$ are concyclic and we are done. If $F$ has color $1$, then since $QR \cdot QE = QP \cdot QD = QB \cdot QF$, $E,R,B,F$ are concyclic and we are done. If all points colored $3,4,5$ lie on only one line, let that line be $\ell'$. Call a point on $\ell'$ good if its color is $3,4$ or $5$. Let $X$ and $Y$ be points on $\ell$ (and not on $\ell'$) colored $1$ and $2$ respectively. Let $P_1$, $P_2$, and $P_3$ (in order from left to right) be good points on $\ell'$ with different colors. WLOG assume the colors of $P_1$, $P_2$, and $P_3$ to be $3$, $4$, and $5$ respectively. Case 1: There exists a good point $P_4$ not colored $4$ either to the left of $P_1$ or to the right of $P_3$. Then circles $(P_1P_3X)$ and $(P_2P_4Y)$ intersect and each have at least $3$ distinct colors. Assuming that $Y \notin (P_1P_3X)$ (if not, just pick a different option for $Y$), then an intersection point of those two circles is either colored $1$ or $2$. Either way, one of those two circles will have $4$ distinct colors, and we are done. Case 2: All good points to the left of $P_1$ or to the right of $P_3$ (if there are any) are colored $4$. Then from condition (1), there exist points $P_5$ and $P_6$, both between $P_1$ and $P_3$, whose colors are $3$ and $5$ respectively. If $P_5$ is to the left of $P_6$, then $(P_1P_6X)$ and $(P_3P_5Y)$ intersect and each have at least $3$ distinct colors. As shown above, this shows there is a circle with $4$ distinct colors. If $P_5$ is to the right of $P_6$, then we have the following $3$ subcases: Case 2a: $P_2$ is to the left of $P_6$. Then $(P_1P_6X)$ and $(P_2P_3Y)$ intersect and each have at least $3$ distinct colors. This shows there is a circle with $4$ distinct colors. Case 2b: $P_2$ is between $P_6$ and $P_5$. Then $(P_1P_2X)$ and $(P_5P_6Y)$ intersect and each have at least $3$ distinct colors. This shows there is a circle with $4$ distinct colors. Case 2c: $P_2$ is to the right of $P_5$. Then $(P_1P_2X)$ and $(P_3P_5Y)$ intersect and each have at least $3$ distinct colors. This shows there is a circle with $4$ distinct colors. In all cases, we have shown that there is a circle with $4$ distinct colors for $n=5$, and we are done.