# Combinatorics (coloring)

I know how to solve the two individual problems (lines alone and circles alone) but not combined.

• The same trick works. You can have any number of lines and any number of circles. – Brian M. Scott Apr 4 '15 at 21:10
• I can't seem to make it work in this case. Could you work it out? – user228783 Apr 4 '15 at 21:15
• Just flip the colors on one side of the line or circle when you add it. Where are you running into trouble? – Brian M. Scott Apr 4 '15 at 21:19
• But doesn't this have more cases? If we added a line inside the added circle? outside? etc – user228783 Apr 4 '15 at 21:21
• What added circle? At each stage you add either a line or a circle and flip the colors on one side of it. It's the same argument whether you add a line or a circle. – Brian M. Scott Apr 4 '15 at 21:24

Let us prove a stronger statement: Let $C_1,\dots,C_m$ be $m$ circles and $L_1,\dots,L_n$ be $n$ lines. Then, with two colour say black and white, we can colour the regions with that every two adjacent regions are differently coloured. We proceed to prove by induction on $m+n$. For the case $m+n=1$ is trivial, as there are only two regions. Now, assume $m+n>1$. If $m\geq 1$, then we can have our colouring $K$ for regions partitioned by $C_1,\dots,C_{m-1},L_1,\dots,L_n$. To obtain a new colouring for regions partitioned by $C_1,\dots,C_{m-1},C_m,L_1,\dots,L_n$, we change all colourings of $K$ for regions inside $C_m$, it will work. Similarly, if it is not the case ($m\geq 1$), then it must be $n\geq 1$, we take $K$ to be the colouring for regions partitioned by $C_1,\dots,C_m,L_1,\dots,L_{n-1}$, then we change all colourings of $K$ for regions on the right-hand-side of $L_n$ (with $L_n$ orientated arbitrarily).