6
$\begingroup$

Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point.

enter image description here

Each intersection point is colored red, green or blue. Prove that it is possible to color all intersection points in a “proper” way, so that any two adjacent points (like $A_i, A_j$) have different colors.

This also means that if you "travel" along an arbitrary line, you will cross $n-1$ intersection points, constantly changing colors from one intersection point to another.

My first (and last) try was to use induction. Obviously for two or three lines, we have one or three intersection points and with three colors available we have the base of induction proved. However, the induction step is more difficult. I was able to prove the induction step if in every possible arrangement of lines it was possible to find a line that divides the plane into two halves with one half having no intersection points. However, I was able to construct counter-examples where such line does not exist.

The last time I tried to solve a similar red-green-blue problem I discovered Ramsey theory. I wonder what I will discover this time :)

|cite|improve this question
$\endgroup$
3
$\begingroup$

Let us assume WLOG that no lines are vertical--if not rotate the plane to make this so [make sure you see that this is indeed possible].

Let us colour the set of points from left to right [no lines are vertical, thus for each line $L$ there is indeed a strict ordering of the points on $L$ from left to right], with the colours 1,2,or 3, as follows.

  1. Colour a leftmost point with the color 1. [As there are only $<n^2$ points there is indeed a leftmost point. Pick one such point arbitrarily]

  2. Let $p$ be a point that satisfies the following: Letting $L_1$ and $L_2$ be the two lines containing $p$ [as only two lines intersect a point there are only two such $L_i$], all points to the left of $p$ on $L_1$ [which recall neither $L_1$ nor $L_2$ is not vertical] have already been colored and all points to the left of $p$ on $L_2$ have already been colored. Then letting $p_i$ be the point immediately to the left of $p$ on $L_i$; $i=1,2$; and writing as $c(p_i)$ the color assigned to $p_i$ for $i=1,2$ [$c(p_i) \in \{1,2,3\}$], let the color $c(p)$ of $p$ be an integer in $\{1,2,3\}$ that is neither $c(p_1)$ nor $c(p_2)$. [There indeed always exists such a $p$ as long as there are still uncoloured points, as a leftmost point of the points not coloured yet always suffices.]

See for yourself that the above algorithm indeed terminates, and that it also terminates with a proper 3-colouring.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.) $\endgroup$ – YiFan Nov 25 '18 at 0:09
  • 1
    $\begingroup$ The leftmost point not colored yet always suffices $\endgroup$ – Mike Nov 25 '18 at 0:10
  • 4
    $\begingroup$ In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.) $\endgroup$ – Misha Lavrov Nov 25 '18 at 4:21
  • 1
    $\begingroup$ @Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$. $\endgroup$ – YiFan Nov 25 '18 at 5:27
  • 1
    $\begingroup$ Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks. $\endgroup$ – Oldboy Nov 25 '18 at 8:50

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.