Page 1 of 15 12311 ... LastLast
Results 1 to 30 of 449

Thread: Four Color Theorem

  1. #1
    Join Date
    Jul 2005
    Posts
    1,704

    Four Color Theorem

    So you only need four color's to color a map? What if all the localaties met at a single point? See the attached diagram. Lets a ssume the lines are perfect and borders intersect at a single point. Would that mean that more than 4 colors are needed?
    Attached Images Attached Images

  2. #2
    Join Date
    Mar 2004
    Posts
    15,801
    Wikipedia: Four color theorem

    The four color theorem states that any plane separated into regions, such as a political map of the counties of a state, can be colored using no more than four colors in such a way that no two adjacent regions receive the same color. Two regions are called adjacent if they share a border segment, not just a point.
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ...
    Skepticism enables us to distinguish fancy from fact, to test our speculations. --Carl Sagan

  3. #3
    Join Date
    Mar 2002
    Posts
    2,379
    There is a book, called Four Colours Suffice that gives the history of the problem. It is a layman's book, but the math level varies. Sometimes it is too simplistic. Other times it goes too fast, but in all, I have a better understanding of the proof than I did before I read it.

  4. #4
    Join Date
    Mar 2004
    Posts
    3,133
    But have they proved it for all colours?

  5. #5
    Join Date
    Mar 2002
    Posts
    2,379
    Quote Originally Posted by worzel
    But have they proved it for all colours?
    I'm not sure I understand what you mean. It is trivial to prove that 3 or fewer colors is not sufficient. All you need is to show that there is a map where 3 colors aren't enough. Here is a simple counterexample: Start with a thick circle with a hole in the center. Section the circle into 3 parts, each of which must be a different color. The hole in the center must also be different from the first 3 colors used on the circle, which proves that 3 colors are too few. For 5 colors, take a 4 color map and arbitrarily change one of the areas to a color that isn't anywhere else on the map. For 6 colors, take the above mentioned 5 color map and change one area to a color that isn't yet used. Do this for as many colors as you have in your crayon box.
    Attached Images Attached Images
    • File Type: jpg d.JPG (5.0 KB, 14 views)

  6. #6
    Join Date
    Apr 2005
    Posts
    11,545
    I know what he means. **bap** now, say you're sorry

    It has long been known that a map on a torus requires seven colors, and seven always suffices. To see that seven is necessary, take a torus, and divide it into bands of seven different regions encircling the torus through its hole. Now, cut a line around the top of the "donut" and slide the outside parts along the line 2 1/2 regions. All seven regions will share a boundary with all six other regions.

  7. #7
    Join Date
    Mar 2004
    Posts
    3,133
    What I acutally meant was although it is true for the traditional colours used on a political map, has it also been proven for, say, 4 slightly different shades of pink.
    Quote Originally Posted by hhEb09'1
    I know what he means. **bap** now, say you're sorry
    Sorry.

  8. #8
    Join Date
    Nov 2002
    Posts
    195
    It doesn't matter which colors you use, as long as they are all different. So, yes, it would work for 4 different shades of pink because they are all different. It would also work for four shades of blue, green, maybe two of red and two of grey, etc.

    Basically, when you have four countries that all touch each other, one of those contries has to be completely surrounded. Notice in jfribrg's diagram, the brown country is completely surrounded. Go ahead and try it yourself on a piece of paper.

    There is, however, an unstated premise: All the countries have to be in one piece. For example, the United States is not in one piece because of Alaska. There are two large "pieces" of the U.S. (and various islands)... If you tried this on the actual map of the Earth, you might not find the 4 color theorem is true (then again, it might be. I've never tried it).

  9. #9
    Join Date
    Mar 2004
    Posts
    3,133
    Quote Originally Posted by zrice03
    It doesn't matter which colors you use, as long as they are all different. So, yes, it would work for 4 different shades of pink because they are all different. It would also work for four shades of blue, green, maybe two of red and two of grey, etc.
    Ok, thanks for the clarification

    There is, however, an unstated premise: All the countries have to be in one piece. For example, the United States is not in one piece because of Alaska. There are two large "pieces" of the U.S. (and various islands)... If you tried this on the actual map of the Earth, you might not find the 4 color theorem is true (then again, it might be. I've never tried it).
    I think you would find that the 4 color theorem is true irrespective of the potential problem you raise, it just isn't the same thing you're describing.

  10. #10
    Join Date
    Apr 2005
    Posts
    11,545
    LOL. Yep. Just take any map of any set of N countries and put an "embassy" for each one, in each one. Then, you need N colors.

  11. #11
    Join Date
    Nov 2002
    Posts
    195
    Quote Originally Posted by hhEb09'1
    LOL. Yep. Just take any map of any set of N countries and put an "embassy" for each one, in each one. Then, you need N colors.
    Exactly.

  12. #12
    Join Date
    Mar 2002
    Posts
    2,379
    Quote Originally Posted by zrice03
    Basically, when you have four countries that all touch each other, one of those contries has to be completely surrounded.
    Basically that is the key, but proving it is the problem.


    Quote Originally Posted by zrice03
    There is, however, an unstated premise: All the countries have to be in one piece.
    Actually, this is stated explicitly in the formal definition of the problem.

    Quote Originally Posted by zrice03
    For example, the United States is not in one piece because of Alaska.
    Hawaii also, but the problem is limited to contiguous areas on a flat (two dimensional) surface that share a border. IIRC, for these purposes, Michigan is a problem too.

  13. #13
    Join Date
    Mar 2004
    Posts
    3,133
    Quote Originally Posted by jfribrg
    Quote Originally Posted by zrice03
    There is, however, an unstated premise: All the countries have to be in one piece.
    Actually, this is stated explicitly in the formal definition of the problem.
    Quote Originally Posted by zrice03
    Exactly.

  14. #14
    Join Date
    Jan 2005
    Posts
    1,939
    Are there any practical applications for the four colour theorem or is it just one of those "neat things" to know like Fermat's Last Theorem and Relativity (Ha! Kidding!)

    Pete

  15. #15
    Join Date
    Mar 2004
    Posts
    3,133
    Quote Originally Posted by peter eldergill
    Are there any practical applications for the four colour theorem or is it just one of those "neat things" to know like Fermat's Last Theorem and Relativity (Ha! Kidding!)

    Pete
    Maybe it's why there are CMYK printers - but that would suggest that there is a three colour theorem waiting to be proved.

  16. #16
    Join Date
    Apr 2005
    Posts
    1,784

    Smile 4 Colours

    It is obviously useful for (game)mapmakers.

  17. #17
    Join Date
    Nov 2003
    Posts
    46
    I spent an entire summer as a kid trying to draw maps that would disprove the theorem. It wasn't a complete waste of time, because it did get me started down the path of scientific inquiry.

  18. #18
    Join Date
    Mar 2004
    Posts
    3,133
    I was so naive when I first saw the problem that I figured that as it was obvious, I would be able to come up with a simple proof and dazzle the world

  19. #19
    Join Date
    Jan 2005
    Posts
    1,939
    My Uncle thought he had a proof of Fermat's Last theorem, less than a page. Even I found his mistake quickly.

    He also had a "proof" that an angle can be trisected. I couldn't follow what he was doing, as it was purely geometrical, which I'm not familiar with

    Well, gotta go!

    Pete

  20. #20
    Join Date
    Jul 2005
    Posts
    1,005
    Quote Originally Posted by jfribrg
    IIRC, for these purposes, Michigan is a problem too.
    I guess the problem would be not that Michigan comes in two pieces (they're easy enough to connect, at least on the map), but that neither Michigan and Illinois nor Indiana and Wisconsin share a border...

  21. #21
    Join Date
    Jul 2005
    Posts
    1,005
    Quote Originally Posted by peter eldergill
    My Uncle thought he had a proof of Fermat's Last theorem, less than a page.
    Maybe it was the same proof Fermat had

  22. #22
    Join Date
    Sep 2004
    Posts
    2,527
    And we try to keep as much water as possible between us and Canada. (Here being Michigan) If the water is blue, does that count as a color?

    I'm with Worzel here.

    And what if the colors run?

    Who among us before they were old enough to know how smart they weren't didn't figure, "Oh, I can beat that, lemme at it..."?

  23. #23
    Join Date
    Jul 2005
    Posts
    1,005
    Quote Originally Posted by Enzp
    And we try to keep as much water as possible between us and Canada. (Here being Michigan)
    Was just there a couple of weeks ago, didn't look like a particularly long bridge

  24. #24
    Join Date
    Apr 2005
    Posts
    11,545
    Quote Originally Posted by peter eldergill
    He also had a "proof" that an angle can be trisected. I couldn't follow what he was doing, as it was purely geometrical, which I'm not familiar with
    Here's a way to trisect an angle.

  25. #25
    Join Date
    Mar 2002
    Posts
    2,379
    Quote Originally Posted by hhEb09'1
    Here's a way to trisect an angle.
    From page 101 of the book "Elements of Abstract Algebra", which provides an interesting use of field theory to provide straightedge-and-compass proofs, this trisection is addressed.

    First let us show how angles may be trisected easily if we allow and incorrect usage of the straightedge. (Apparently this practical construction was known to ancient geometers.)


    As with other math problems, the "rules" are clearly defined. From the same book, here are the rules:
    (1)the points (0,0) and (1,0) are constructible. Any two points of the plane may be chosen for (0,0) and (1,0) and the distance between them taken as the unit length.
    (2) A circle with a constructible point as center and a constructible length as radius is constructible. A constructible length is the distance between two constructible points.
    (3) The intersection of two constructible lines is a constructible point.
    (4) The points (or point) of intersection of a constructible line and a constructible circle are constructible
    (5) The points (or point) of intersection of two constructible circles are constructible
    Step 3 in the link from the previous post is the illegal operation. The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.

    The book then provides a single counterexample. First, the constructible points and operations are restated in terms of complex numbers, and a proof is given that these operations and points form a field. It then shows using field theory that it is impossible to trisect a 60 degree angle.

  26. #26
    Join Date
    Mar 2004
    Posts
    3,133
    Quote Originally Posted by jfribrg
    Step 3 in the link from the previous post is the illegal operation. The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.
    You could use the compass to measure the chord and then mark that off from E or F.

  27. #27
    Join Date
    Apr 2005
    Posts
    11,545
    Quote Originally Posted by jfribrg
    Step 3 in the link from the previous post is the illegal operation.
    Step 2 is also "illegal".

    However, I use the straightedge legally, throughout.
    The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.
    No, it's not. As worzel points out, you can use that angle to easily construct a copy anywhere else, including between the original angle.

  28. #28
    Join Date
    Sep 2004
    Posts
    2,527
    Montebianco - which bridge? Try walking that Mackinac bridge, she is longer than she looks. Every so often a car or truck blows over on it. We have our ways...

  29. #29
    Join Date
    Mar 2004
    Posts
    3,133
    Two questions.

    The first to jfribrg or anyone else who knows the answer. What purpose are those 5 rules of geometric construction supposed to serve given that they appear not to define what can actually be done, geometrically, with a straight edge and compass?

    The second to hhEb09'1. Did you come up with that trisection yourself?

  30. #30
    Join Date
    Apr 2005
    Posts
    11,545
    Quote Originally Posted by worzel
    The second to hhEb09'1. Did you come up with that trisection yourself?
    The neusis or verging "cheat" trisections have been known for over two thousand years. That particular one is my modification of Archimedes's--which, according to The Book of Numbers by Conway and Guy, uses a marked ruler--which is an incorrect use of a ruler, as jfribrg's link says. Apparently, a lot of people know about the incorrect use of rulers, so I changed it to an incorrect use of a compass instead.

Similar Threads

  1. Simple Color and Color Perception Question.
    By BigDon in forum Space/Astronomy Questions and Answers
    Replies: 6
    Last Post: 2012-Jul-04, 04:51 PM
  2. Color Color diagram (U-B) (B-V) how to read it?
    By tu144 in forum Space/Astronomy Questions and Answers
    Replies: 8
    Last Post: 2011-Apr-08, 09:12 AM
  3. The Salary Theorem
    By Tranquility in forum Off-Topic Babbling
    Replies: 6
    Last Post: 2005-Apr-28, 09:38 PM
  4. kmar's theorem
    By kmarinas86 in forum Against the Mainstream
    Replies: 26
    Last Post: 2004-Jul-09, 11:50 PM
  5. Multiverse Theorem
    By String Fan in forum Against the Mainstream
    Replies: 1
    Last Post: 2004-May-07, 03:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •