Determination

The correct answer is 204,985,467,666,432. (over 200 trillion)

 

A rough estimate of the answer can be found as follows:

 

You have four colors, red, green, blue, and yellow.

 

You decide to color Washington first. There are 4 ways to color Washington by itself: red, green, blue, and yellow.

 

Washington = 4

 

Next you color Oregon. For each color of Washington, there are 3 other colors you could use for Oregon, without making Oregon the same color as Washington. That means there are 12 valid ways to color Washington and Oregon: red/green, red/blue, red/yellow, green/red, green/blue, green/yellow, blue/red, blue/green, blue/yellow, yellow/red, yellow/green, yellow/blue.

 

Washington/Oregon = 4 x 3 = 12

 

You decide to color California next. For each of the 12 combinations of Washington/Oregon, there are 3 more choices for the color of California, because it can't match Oregon. Here they are, in shorthand: RGR, RGB, RGY, RBR, RBG, RBY, RYR, RYB, RYG, GRG, GRB, GRY, GBR, GBG, GBY, GYR, GYG, GYB, BRG, BRB, BRY, BGR, BGB, BGY, BYR, BYG, BYB, YRG, YRB, YRY, YGR, YGB, YGY, YBR, YBG, YBY

 

Washington/Oregon/California = 4 x 3 x 3 = 36

 

Next you color Neveda. For each of the the 36 combinations of Washington/Oregon/California, there are 2 more choices for Nevada, because it can't match Oregon or California. (example: Washington/Oregon/California are red/green/blue, Nevada can be either red or yellow.)

 

Washington/Oregon/California/Nevada = 4 x 3 x 3 x 2 = 72

 

Next you color Idaho. Now it gets complicated. Sometimes, Washington and Nevada are the same color, with Oregon being a second color. That leaves 2 more choices for Idaho. Sometimes Washington and Nevada are different, and Oregon must be a third color, leaving only 1 choice for Idaho. Washington and Nevada will be the same color 1/3rd of the time. (In the 36 combinations above, 12 of them have Washington and California the same. The same would apply to Washington and Nevada.) That means, on average, there are 1 and 1/3rd choices for Idaho, or 4/3rds.

 

Washington/Oregon/California/Nevada/Idaho = 4 x 3 x 3 x 2 x 4/3 = 96

 

What soon happens is that the states fall into a pattern of sometimes being forced to a single color (because it is already touching three differently colored states), sometimes having a choice of 2 colors, and occasionally having 3 choices, or a fraction between 1 and 2. Also, if you don't do it right, you can end up trying to color a state that is already touching four states of different colors. If that happens, an earlier choice is invalid, and you have to back up.

 

From this, we could make a rough estimate that, on average, as you go to color each state, you will have 2 choices for colors. That means:

 

48 states = 2 x 2 x 2 x ... x 2 x 2 x 2 = 2 to the 48th power

 

2 to the 48th is a big number... 281,474,976,710,656. So it's a very rough estimate, but a good start.

 

I wrote a program to go through the real permutations, instead of the estimate of 2 choices per state. The actual number of color combinations for the 48 contiguous states is 12,811,591,729,152, or about 13 trillion. (That number is closer to 2 to the 44th, rather than our estimate of 2 to the 48th.)

 

But for each one of the almost 13 trillion ways to color the first 48 states, there are still 4 ways to color Alaska, and 4 ways to color Hawaii. No borders, so they never conflict with other colors, and there are always 4 choices. So the final answer is:

 

50 states = 12,811,591,729,152 x 4 x 4 = 204,985,467,666,432

 

By the way:

 

I didn't write the program just to find and count the combinations. I'm not using red, green, blue and yellow in the penny map. The colors are shiny copper, dull copper, and in-between copper, that I have to try to stretch into two colors. It's tough. You can see it in the pictures of The Original. The worst part is Nebraska/Kansas/Oklahoma, but there's also a dark band from Louisiana looping all the way around to Arizona.

 

Let's call the colors, from shiniest to dullest, 1, 2, 3, and 4. The program tries to find a combination with the most borders with colors 1 and 4. For borders that can't be 1 and 4, it looks for the most borders 1 and 3, and 2 and 4. Finally, when the only options are 1-2, 2-3, or 3-4, it prefers 1-2 and 2-3 over 3-4, because tests show that 3 and 4 are the closest together, and hardest to tell apart. In other words, the program tries to maximize the contrast.

 

The program checks all 12.8 trillion combinations of colors for the 48 contiguous states, and finds the combination with the most contrast, in under 10 seconds. (!)

 

Once I had that program working, I added a few aesthetic options. For example, you can color Arizona and Colorado the same, and Utah and New Mexico the same, because they only touch at the corners. But it doesn't look right. It looks like the BMW logo. I added an option so that the program looks for the most contrast, but skips combinations with only two colors on those four states.

 

Another optional filter: Texas and Colorado are both big states, and they are only separated by one row of pennies in Oklahoma. It doesn't quite look right if Texas and Colorado are the same color. (Eventually, I had to give that up, in favor of some other aesthetics. But the option is still coded in the program.)

 

This is where using a computer is a huge help. Changing the color of one state has a "ripple effect", where several or many other states are also forced to change, so that bordering states aren't the same. If I change one state because I know it will look better, it would take a person hours or days to find the best combination among millions of new "ripple changes". Once I get the program to work the logic differently for a particular state, the rest of the program finds the next best combination in... ding!... less than 10 seconds.

 

I ended up with a map that only has two states with color 3, and two borders with color 3 next to 4. I made Alaska color 3 also, just because it can be any color, I had enough of them, and I was running out of good matching pennies in the other colors.