0
$\begingroup$

Question: A plane is divides into regions by drawing a finite no. of straight lines. Show that it is possible to color each of these regions red or green in such a way that no two adjacent regions have the same color.

This question has left me clueless, and I have no idea as to how this can be proved. A hint might help...

$\endgroup$

marked as duplicate by Osheen Sachdev, Community Oct 10 '16 at 5:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @Arthur It has to be proved using induction... $\endgroup$ – Osheen Sachdev Oct 10 '16 at 5:28
1
$\begingroup$

Let the $i$th line be given by $a_i x + b_i y + c_i=0$. Note that $a_i x + b_i y + c_i$ is positive on one side of the line and negative on the other side. Thus $$f(x,y)=\prod_i\left(a_i x + b_i y + c_i\right)$$ is a function which changes sign whenever you cross a line. Color red if $f$ is positive and green if $f$ is negative.

In simpler terms, for every line you can construct a function which is positive on one side of the line and negative on the other side. Say for the $i$th line this function is $f_i(x,y)$.

If you multiply all these functions together, you get a function which changes sign whenever you cross a line, i.e. no two adjacent regions have the same sign. This is precisely the function you are asked to construct.

$\endgroup$
  • $\begingroup$ I don't quite understand what you have done...can you elaborate a bit? $\endgroup$ – Osheen Sachdev Oct 10 '16 at 5:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.