0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The same trick works. You can have any number of lines and any number of circles. $\endgroup$ – Brian M. Scott Apr 4 '15 at 21:10
  • $\begingroup$ I can't seem to make it work in this case. Could you work it out? $\endgroup$ – user228783 Apr 4 '15 at 21:15
  • $\begingroup$ Just flip the colors on one side of the line or circle when you add it. Where are you running into trouble? $\endgroup$ – Brian M. Scott Apr 4 '15 at 21:19
  • $\begingroup$ But doesn't this have more cases? If we added a line inside the added circle? outside? etc $\endgroup$ – user228783 Apr 4 '15 at 21:21
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Apr 4 '15 at 21:24
0
$\begingroup$

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).

$\endgroup$

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.