My Math Forum Coloring problem

 Algebra Pre-Algebra and Basic Algebra Math Forum

 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post kriegor Applied Math 2 May 22nd, 2012 01:19 AM Nekochan Applied Math 0 January 28th, 2011 11:39 AM ry. Applied Math 0 April 13th, 2010 05:45 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top