Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: 4 colors problem
Replies: 86   Last Post: Mar 13, 2014 4:36 PM

 Messages: [ Previous | Next ]
 stumblin' in Posts: 58 Registered: 3/3/14
Re: 4 colors problem
Posted: Mar 3, 2014 11:18 PM

I have (what I hope is) a simple line of thought that shows why 4 color solution works only half the time in some situations.

Suppose we're coloring a map of countries, which are shaped as squares of equal size and lined up in a row, row after row, using only 4 colors, with no two neighboring countries sharing the same color.

Let a=blue, b=green, c=red, d=yellow, then

A = [ [a b c d]
[c d a b] ]

matrix A shows the coloring scheme of 8 countries, with no two countries sharing the same color, as if looking down on a map seeing only the coloring of each country.
It's the same as writing out,

A = [ [country1 blue, country2 green, country3 red, country4 yellow]
[country5 red, country6 yellow, country7 blue, country8 green] ]

but we're focusing on the coloring scheme only by using letters, a, b, c, d.

The coloring scheme can expand to the left or right, above or below to include other countries using the matrix A as a unit pattern.

To add countries to the left, use the matrix A in a right-to-left fashion.

[ [c d][a b c d]
[d a b][c d a b] ]

to ensure that the condition of 4 coloring solution remains intact.

To add countries to the right,

[ [a b c d] [a b c]
[c d a b] [c d a b] [c d] ]

To add more rows of countries above or below the matrix A,

[ [a b c d]
[c d b a]
[a b c d] <-- matrix A
[c d b a] <-- matrix A
[a b c d]
[c d b a] ]

This ensures that the coloring of a map will follow the "no two neighboring countries sharing the same color" condition no matter how big the map gets and no matter how many countries get added to existing countries, row-wise, column-wise.

This proves that the 4-color theorem is valid.
Situation changes when the map has a city whose horizontal length is larger (by a multiple of integers) than the rest of the countries on the map.
Specifically, if it's larger by an odd number (3,5,7,9...) then the 4 color theorem holds. If it's larger by an even number (2,4,6,8...) the theorem fails.

Here's an example,

matrix B has 12 cities in a row, with a total of 5 rows, except the middle row has only 7 cities because the 2nd city from the left is 6 cities long.
It's longer by an even number, 6, so 4 color solution fails.
[d d d d d d] denotes one city colored in d(= yellow).
Take each "d" and make sure there are no other d's in the next column adjacent to the d in [d d d d d d] and if there are, swap them with the next value on that column.

B = [ [c d a b c d a b c d a b]
[a b c d a b c d a b c d]
[c [d d d d d d] b c d a b]
[a b c d a b c d a b c d]
[c d a b c d a b c d a b] ] becomes

B = [ [c d a d c d a d c d a b]
[a b c b a b c b a b c d]
[c [d d d d d d] b c d a b]
[a b c b a b c b a b c d]
[c d a d c d a d c d a b] ]
^ ^

The pointers at the bottom of the matrix show the columns that swapped b and d to follow the "no two neighboring countries having same color" condition. The column indicated by the second pointer has 3 b's on top of each other, showing that the 4 color solution fails.

Here's an odd number example that succeeds.

matrix C is similar to matrix B except the longer city is 5 times longer compared to the surrounding cities, and the 4 color solution works.

C = [ [c d a b c d a b c d a b]
[a b c d a b c d a b c d]
[c [d d d d d]a b c d a b]
[a b c d a b c d a b c d]
[c d a b c d a b c d a b] ] becomes

C = [ [c d a d c d a b c d a b]
[a b c b a b c d a b c d]
[c [d d d d d]a b c d a b]
[a b c b a b c d a b c d]
[c d a d c d a b c d a b] ]
^
This time there was only pointer at the bottom of the matrix C indicating one column that swapped the values to follow the 4-color condition.

When there is a city on the map whose horizontal length is longer by a multiple of integers (2,3,4...) compared to the rest of the cities on the map, then 4-color solution succeeds if the city is longer by odd numbers (3,5,7...), and fails if it's longer by even numbers (2,4,6,8...).

Date Subject Author
3/3/14 stumblin' in
3/3/14 Brian Q. Hutchings
3/3/14 stumblin' in
3/4/14 g.resta@iit.cnr.it
3/3/14 stumblin' in
3/4/14 stumblin' in
3/4/14 g.resta@iit.cnr.it
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 g.resta@iit.cnr.it
3/4/14 magidin@math.berkeley.edu
3/4/14 stumblin' in
3/4/14 Port563
3/4/14 stumblin' in
3/4/14 Brian Q. Hutchings
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 Port563
3/4/14 stumblin' in
3/4/14 Brian Q. Hutchings
3/4/14 stumblin' in
3/4/14 stumblin' in
3/4/14 Brian Q. Hutchings
3/4/14 g.resta@iit.cnr.it
3/4/14 stumblin' in
3/4/14 Port563
3/4/14 stumblin' in
3/5/14 stumblin' in
3/5/14 magidin@math.berkeley.edu
3/5/14 stumblin' in
3/5/14 magidin@math.berkeley.edu
3/5/14 quasi
3/5/14 stumblin' in
3/5/14 magidin@math.berkeley.edu
3/5/14 stumblin' in
3/5/14 quasi
3/5/14 magidin@math.berkeley.edu
3/5/14 Brian Q. Hutchings
3/5/14 stumblin' in
3/5/14 magidin@math.berkeley.edu
3/5/14 stumblin' in
3/5/14 Brian Q. Hutchings
3/5/14 Virgil
3/5/14 stumblin' in
3/5/14 stumblin' in
3/5/14 stumblin' in
3/5/14 stumblin' in
3/5/14 stumblin' in
3/5/14 stumblin' in
3/5/14 Virgil
3/5/14 stumblin' in
3/6/14 Virgil
3/6/14 Virgil
3/6/14 Brian Q. Hutchings
3/6/14 stumblin' in
3/6/14 ross.finlayson@gmail.com
3/7/14 Brian Q. Hutchings
3/7/14 Robin Chapman
3/6/14 stumblin' in
3/6/14 stumblin' in
3/7/14 magidin@math.berkeley.edu
3/7/14 Peter Percival
3/7/14 Peter Percival
3/6/14 stumblin' in
3/7/14 stumblin' in
3/7/14 magidin@math.berkeley.edu
3/7/14 Peter Percival
3/7/14 Peter Percival
3/7/14 stumblin' in
3/7/14 stumblin' in
3/9/14 stumblin' in
3/9/14 Peter Percival
3/9/14 stumblin' in
3/9/14 magidin@math.berkeley.edu
3/9/14 Brian Q. Hutchings
3/9/14 stumblin' in
3/9/14 stumblin' in
3/11/14 stumblin' in
3/11/14 Brian Q. Hutchings
3/13/14 stumblin' in
3/13/14 Brian Q. Hutchings
3/13/14 stumblin' in