- **Algebra**
(*http://mymathforum.com/algebra/*)

- - **Coloring problem**
(*http://mymathforum.com/algebra/19972-coloring-problem.html*)

Coloring problemHello! I solved a problem, but I can't prove it with induction. Here it is the problem:Draw n arbitrary circles in the plane and suppose that the obtained image is a map. Prove that we can color this map with 2 colors such as two regions having a common border have different colors. The solution:For each region count the circles which contains this region in their interior. If this number is even we color the region with red, otherwise with black. We prove this by induction.For n = 1 it is trivial. For n = 2, we consider the three possible positions of the two circles, and we see that the above assumption is true. We assume, that the statement is true for n circles, how we can prove for n + 1 ? Please help :) Many Thanks, Crouch. |

Re: Coloring problemWhat have you tried so far? More importantly, have you drawn a few pictures (up to 4 circles would be nice)? |

Re: Coloring problemYes, I drew pictures. But I can't generalize for n... When we have n circles, and the coloring is good, we put the n+1.th circle. How many new regions will we have? I don't know how can we prove this... |

Re: Coloring problemAll regions outside new circle don't change color, those inside do. If two adjacent regions have different colors, both change or both don't and remain different. If region is split by circle border, one part changes color so parts have different color. It means that new circle doesn't break coloring rule. |

All times are GMT -8. The time now is 06:35 PM. |

Copyright © 2019 My Math Forum. All rights reserved.