My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Reply
 
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.
Crouch is offline  
 
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)?
DLowry is offline  
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...
Crouch is offline  
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.
octahedron is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

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





Copyright © 2018 My Math Forum. All rights reserved.