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 4, 2014 1:43 PM

It's easy to see that 4 color solution fails with the map represented by matrix B.

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

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] ]

The above map was colored according to "no two neighboring countries sharing the same color" condition of the 4 color solution.
[d d d d d d] is one long country colored in yellow, 6 times longer than the rest of the countries on a map.
From the 3rd and 4th columns, the "d" on the third column has two adjacent d's on the next column, one row above and one row below it, so the d's on the 4th column need to swap with the values next to it on the column, away from the center (doing so is safe since the changed values observe the "no two neighboring countries sharing same color" condition.

a b a d
c d c b
d d becomes=> d d
c d c b
a b a d

Same happens with the 7th and 8th columns, and resulting matrix B is,

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] ]

With 3 b's (3 countries stacked on top of each other with same coloring of
b(=green), indicating that for when a map has a country whose horizontal length is longer than the rest of the countries by an even number (2,4,6,8...), in this case it's longer by 6 times, the 4 color solution fails.

You can draw lines on a piece of paper, horizontally and vertically, and color each square according to the coloring scheme indicated by letters a,b,c,d, in the matrix B, and see that the longer country in the middle row results in three countries sharing the same color on the next column where the longer country ends. This should be proof enough for the validity of the counterexample.

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