Another big math problem solved!
Mar. 22nd, 2008 12:03 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
javasaurusThis problem doesn't have the romance of the great classics, like Fermat's last theorem, or the Riemann hypothesis, but it's a neat question that you don't need a degree in mathematics to understand. It was first proposed about thirty years ago, and was only recently solved.
Known as the road coloring problem, the basic idea is this: you've got a set of locations (maybe houses in a city) and paths between them (roads). Color all the roads (some will be the same color). For any given destination, can you give a set of directions (road colors) that will work no matter where you start. For example, suppose the directions to the Baltimore Aquarium were "orange blue blue red green" -- then from anywhere in Baltimore you could take an orange street, then a blue, another blue, a red, and a green, and you'd be there! One trick, of course, is how to set up the colors. For the problem to work, you need certain restrictions on the map (so you are physically able to get from any point to any other point, and you can't get stuck in an infinite loop, like being stuck in a traffic circle!)
The wikipedia link above has a better, mathematical example.
Known as the road coloring problem, the basic idea is this: you've got a set of locations (maybe houses in a city) and paths between them (roads). Color all the roads (some will be the same color). For any given destination, can you give a set of directions (road colors) that will work no matter where you start. For example, suppose the directions to the Baltimore Aquarium were "orange blue blue red green" -- then from anywhere in Baltimore you could take an orange street, then a blue, another blue, a red, and a green, and you'd be there! One trick, of course, is how to set up the colors. For the problem to work, you need certain restrictions on the map (so you are physically able to get from any point to any other point, and you can't get stuck in an infinite loop, like being stuck in a traffic circle!)
The wikipedia link above has a better, mathematical example.
