So I posted a picture of South America that I could instantly see had way more colors on it than it actually needed. How do I know this? My friends, let me tell you the way of... graph theory.
Having all those funny-shaped countries isn't convenient at all, now is it? Wouldn't it be nicer if they were easier to deal with... say, points?
Let's give Brazil some friends.
Here's where the math comes in- we're going to draw lines if there's a "symmetric relationship" between the two points. In this case, my symmetric relationship is "borders". You can't share a border with someone without having them border you, so I just draw a straight line (more about this at the end).
Now, we can see the essence of the problem. Color in the points such that no points with a line between them are the same color.
(This took me a few stops and starts- note that I forgot a few borders in the first frame, and that Argentina should be black, not green).
I ended up with this, and wasn't able to reduce any further.
Thus, you need four colors to color this map of South America.
This is actually a pretty famous problem - the Four Color Theorem. It's generally held that the maximum number you need to color any map is 4, although as the Wiki article says, it was proved by computer so ymmv. Or, mathematically, "the chromatic number of any planar graph is less than or equal to 4."
In this smaller case, I used a branch of mathematics called graph theory. Graph theory runs on vertices and edges: a graph is defined to be a collection of vertices V and edges E, [V,E]. You can also have a directed graph, or "digraph", of vertices V and arcs A, [V,A]. Digraphs don't make much sense in the context of this problem, but they're fun to think about and maybe I'll put up a teaser about them later.
The main concept I used to color South America is chromatic number. It's possible to force a graph to be colored with as many as n-1 colors, where n is the number of vertices; however, the chromatic number (the squiggly X is called a "xi", pronounced "khi") is the least number of colors needed. Given that there exist cycles in the graph of South America, you need at least three; in fact, before I drew in the borders between Argentina and Paraguay, the graph was three-colorable.