Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
stumblin' in

Posts: 58
Registered: 3/3/14
Re: 4 colors problem
Posted: Mar 3, 2014 11:18 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
Read 4 colors problem
stumblin' in
3/3/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/3/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
g.resta@iit.cnr.it
3/3/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
g.resta@iit.cnr.it
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
g.resta@iit.cnr.it
3/4/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
Port563
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
Port563
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read there should be a noncomputer proof of 4CT, I agree
Brian Q. Hutchings
3/4/14
Read Re: 4 colors problem
g.resta@iit.cnr.it
3/4/14
Read Re: 4 colors problem
stumblin' in
3/4/14
Read Re: 4 colors problem
Port563
3/4/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/5/14
Read Re: 4 colors problem
quasi
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
quasi
3/5/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/5/14
Read also, what is the spatial analog
Brian Q. Hutchings
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/5/14
Read Re: 4 colors problem
Virgil
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
stumblin' in
3/5/14
Read Re: 4 colors problem
Virgil
3/5/14
Read Re: 4 colors problem
stumblin' in
3/6/14
Read Re: 4 colors problem
Virgil
3/6/14
Read Re: 4 colors problem
Virgil
3/6/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/6/14
Read Re: 4 colors problem
stumblin' in
3/6/14
Read Re: 4 colors problem
ross.finlayson@gmail.com
3/7/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/7/14
Read Re: 4 colours problem
Robin Chapman
3/6/14
Read Re: 4 colors problem
stumblin' in
3/6/14
Read Re: 4 colors problem
stumblin' in
3/7/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/7/14
Read Re: 4 colors problem
Peter Percival
3/7/14
Read Re: 4 colors problem
Peter Percival
3/6/14
Read Re: 4 colors problem
stumblin' in
3/7/14
Read Re: 4 colors problem
stumblin' in
3/7/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/7/14
Read Re: 4 colors problem
Peter Percival
3/7/14
Read Re: 4 colors problem
Peter Percival
3/7/14
Read Re: 4 colors problem
stumblin' in
3/7/14
Read Re: 4 colors problem
stumblin' in
3/9/14
Read Re: 4 colors problem
stumblin' in
3/9/14
Read Re: 4 colors problem
Peter Percival
3/9/14
Read Re: 4 colors problem
stumblin' in
3/9/14
Read Re: 4 colors problem
magidin@math.berkeley.edu
3/9/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/9/14
Read Re: 4 colors problem
stumblin' in
3/9/14
Read Re: 4 colors problem
stumblin' in
3/11/14
Read Re: 4 colors problem
stumblin' in
3/11/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/13/14
Read Re: 4 colors problem
stumblin' in
3/13/14
Read Re: 4 colors problem
Brian Q. Hutchings
3/13/14
Read Re: 4 colors problem
stumblin' in

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.