Taking Yogi Berra’s Advice
"When you come to a fork in the road, take it!" Bad advice for Joe Garagiola, but good advice for computers.
January 24, 2014 - 11:58 am
Let’s take a road trip. We’re going to visit all the capitals of all the 48 contiguous states, starting from Denver.
Now, since we’re taking vacation days to do this, we don’t want to visit any capital more than once, and we want to do this in the least time, or in the shortest distance traveled, which is pretty much the same thing.
Starting from Denver, if we only want to visit one other state capital, planning the trip is easy. Denver to Cheyenne. Boom. Two capitals is easy — you can either go Denver to Cheyenne to Topeka, or Denver to Topeka to Cheyenne. Add in Santa Fe, well, there are several routes. Ignoring, for the sake of keeping my readers awake, some details, basically as we expand the number of cities, we have to explore every possible ordering of the cities. So if we stay in Denver, visiting exactly one capital, we have exactly one route. Visit one other city, we have two choices of trip plan — Denver Cheyenne Denver, or Cheyenne Denver Cheyenne. Visit two other cities — so three cities total — and there are six choices. (Remember this includes trips where someone wants to start and end in Santa Fe or, Gods forbid, Topeka.) So, no other cities, you have 1 choice. One other city, you still only have 2 choices. Two other cities, you have six route choices.
Three other cities? Well, you can use all the routes for two other cities, and go to the new city from each of them. So you multiply the number of routes you’ve already got by the total number of cities. In other words, if we have n cities, we want n × n-1×n-2 … 1.
Many of you already recognize this as n! — “n factorial” — which is an important idea in a lot of different areas of math.