
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
June 30th, 2011, 07:39 AM  #1 
Member Joined: Dec 2009 Posts: 65 Thanks: 0  Coloring problem
Hello! 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. 
July 1st, 2011, 01:47 PM  #2 
Senior Member Joined: Nov 2010 Posts: 502 Thanks: 0  Re: Coloring problem
What have you tried so far? More importantly, have you drawn a few pictures (up to 4 circles would be nice)?

July 2nd, 2011, 12:46 AM  #3 
Member Joined: Dec 2009 Posts: 65 Thanks: 0  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 n+1.th circle. How many new regions will we have? I don't know how can we prove this...

July 4th, 2011, 03:53 PM  #4 
Senior Member Joined: Jul 2011 Posts: 118 Thanks: 0  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.


Tags 
coloring, problem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Edge coloring of the cube  kriegor  Applied Math  2  May 22nd, 2012 01:19 AM 
Graph theory : coloring edges  Nekochan  Applied Math  0  January 28th, 2011 11:39 AM 
digraph: cycle of an even length and coloring the vertices  ry.  Applied Math  0  April 13th, 2010 05:45 AM 