My Math Forum

My Math Forum (
-   Algebra (
-   -   Coloring problem (

Crouch June 30th, 2011 08:39 AM

Coloring problem

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,

DLowry July 1st, 2011 02:47 PM

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

Crouch July 2nd, 2011 01:46 AM

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

octahedron July 4th, 2011 04:53 PM

Re: Coloring problem
All 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.