The Traveling Salesman Problem (greatly simplified)

Mechaniker

The Puzzler of 01/14/2012:

A traveling salesman is assigned to visit all 48 contiguous states by car, but can enter each state only once. He starts in Delaware. What is the last state he visits?

How can anyone not solve this puzzler in 15 seconds or less?

dadoctah

I actually tried to work out a trip just like this once, and discovered there are a lot of different paths you can take, but certain parts of the sequence are heavily constrained. You can also, I believe, start in Pennsylvania and end in the same state that the "official" answer designates, but that's the only other choice.

And not only is the last state completely determined by the stated restrictions, the last *seven* states will always be the same, and there is only one order you can take them in.

Mechaniker

"And not only is the last state completely determined by the stated restrictions, the last *seven* states will always be the same, and there is only one order you can take them in."

What if the starting state, instead of being Delaware, were Maine?

Mechaniker

dado — "I actually tried to work out a trip just like this once, and discovered there are a lot of different paths you can take, but certain parts of the sequence are heavily constrained."

Problems such as these are addressed in a branch of mathematics called Graph Theory. It has many real-world applications (such as determining optimal truck delivery routes) in the fields of Operations Research and Management Science. To try your hand at some simple tutorials from a prof at the University of Tennessee, see Graph Theory Tutorials.

dadoctah

Mechaniker: if the starting state is Maine, the next state must be New Hampshire, because it's the only one that borders Maine. After that you can only go to Vermont or Massachusetts.

If you go to Massachusetts first, you then have to hit either New York, Rhode Island or Connecticut next. If you do New York, you're stuck because you've cut off Vermont on one side from R.I. and Conn. on the other, so stay out of New York just yet. If you go from Mass. to Conn., same problem: you have to either miss Vermont or R.I. after you've taken care of New York. And if you do Rhode Island now, your only following choice is Conn. which will again lock you out of Vermont after you then move on to the only option for the step after. So going from New Hampshire to Massachusetts is out. You have to do Vermont after New Hampshire.

So after Vermont, you have the same problem if you next try to do New York: three New England states and the rest of the country, and you're unable to get to one group to the other. Which means after Vermont must come Massachusetts. If you go to Connecticut after that, Rhode Island is cut off from the remaining states, so that doesn't work; you have to do Rhode Island, *then* Connecticut. And at this point the only next step is New York.

(Notice that New York and New Hampshire are the only states that make the map of the Lower 48 fall into two unconnected pieces if you remove them. That makes them special in a problem like this.)

So, to recap, first seven states *must* be Maine > New Hampshire > Vermont > Massachusetts > Rhode Island > Connecticut > New York, and they must be in that order. After that you do Pennsylvania and New Jersey, and it doesn't really matter which one you do first, or if you do them one after the other right now. Other places along the way where you're going to have your route tightly constrained for you are the Washington/Oregon/Idaho set and a couple of overlapping triplets (the Carolinas and Georgia, and Georgia/Alabama/Florida).

Mechaniker

@ dadoctah ...

You certainly put a lot of thought into this puzzler. Yes, the salesman must either start or finish in Maine if he is to visit each state once and only once. And New York state is unique in that it forms a barrier between the New England states and the remaining states — once past NY, going in either direction, the salesman can never return to the section he just left, be it New England or the lower states.

Some interesting solutions to 48-state problems from the Computer Sciences department at Carnegie-Mellon are given below:
Interesting Map Problems — CS@CMU

Hamitonian circuits/paths are similar mathematically to map-coloring problems, so that is why the two topics are discussed together in the above paper.

Hamiltonian circuits/paths (it is a circuit if the salesman returns to his starting point; it is a path if he does not) are extremely difficult to find, or even to show that one exists in a given problem. There is no algorithm that leads directly to a solution, or even one that tells if a solution exists. There are ad hoc heuristic approaches for some problems, however.

Hamitonian circuits/paths and map-coloring form a branch of mathematics called Graph Theory. The theory has numerous applications in the hard sciences, electrical engineering (designing complex circuit boards, for example), the biological sciences, and businesses (delivery truck routing comes to mind).

A brief, non-mathematical primer on Graph Theory is:
Combinatorics: The Fine Art of Counting
Week 8 Lecture Notes: Graph Theory — MIT

---

Below is a problem one may want to try. It has historical significance (google "Hamilton's icosian" if you are curious). Hamilton developed it into a child's board game with a circular mahogany board, ivory pegs to insert into the nodes (holes) and twine to string around the pegs to mark the pathways. Hamilton sold all rights to the game for £25 in the 1850's. Today an original game is worth about $500,000. BTW, the Irish-born Hamilton, 1805-1865, may have been the most brilliant mathematician of the 19th century.

The figure itself is just the projection of a Dodecahedron upon a plane.

Question #1: Starting at any node ("dot") can one progress along the lines around the figure through all the nodes without passing through the same node twice?
If so, then one has traced out a Hamiltonian path.

Question #2: Can one do the same as above but return to the same node from which one started?
If so, then one has traced out a Hamitonian circuit.

I won't say beforehand whether any path or circuit exists.



Have a go!

littlemouse

@Mechaniker: "How can anyone not solve this puzzler in 15 seconds or less?"

Stealing from Jim Kelly in Enter the Dragon, "I'll be too busy looking good."

Seriously, most people don't have the map of the U.S. memorized. A little pomposity goes a long way. Less goes even farther.

There is no unique solution if Maine is the starting state.

shadowfax

Except that the puzzle (at least as quoted in this thread - I missed that show) doesn't say anything about not being allowed to travel through Canada, which greatly opens up the possibilities.

dadoctah

You certainly put a lot of thought into this puzzler. Yes, the salesman must either start or finish in Maine if he is to visit each state once and only once. And New York state is unique in that it forms a barrier between the New England states and the remaining states — once past NY, going in either direction, the salesman can never return to the section he just left, be it New England or the lower states.

Technically, New York isn't unique because the same is true of New Hampshire: it's just that as a barrier it separates the single state of Maine from the entire rest of the country.

And yes, I've put a lot of thought into it, but years before it became a puzzler. I wanted to work out an actual route and see if it was feasible. It got a little hinky when one of the routes wanted me to go directly from Oklahoma into New Mexico; there's a short section of border there but not a lot of major roads cross it, so while it's actually doable it's not in any sense practical.

And then there's the "New Madrid Bend", where the states of Kentucky, Tennessee and Missouri meet, not at a single point but at three different points a few miles apart.

Mechaniker

mouse — "I'll be too busy looking good."

If you say so — post a pic and let us decide.

Mechaniker

dadoctah "Technically, New York isn't unique because the same is true of New Hampshire: it's just that as a barrier it separates the single state of Maine from the entire rest of the country."

... which makes NY unique. BTW, do you know Ms Mouse? 'night all.

dadoctah

Apologies for resurrecting a dormant thread, but I just got the latest issue of Math Horizons, a magazine published by the Mathematical Association of America, and one of the articles discusses precisely the problem used to set up this Puzzler. Using an algorithm that they go into in the article (and provide links to further resources), they came up with the "most efficient" path through the geographic centers of all 48 contiguous states. The basic idea is that you lay out any random route from one state to another until you return to your starting point, then pick an unvisited state and do likewise, until you have some set of closed circuits that between them hit all the target points. Then you use a rule that they define to "break" pairs of connections in each partial route and join them to another partial route, repeating this until all have been combined into a single route.

There's additional discussion of similar routes through even larger sets of points, including one that visits hundreds of thousands of points.

The shortest route going through the 48 state capitals is shown here:

Note that this cannot be the route in the Puzzler because an additional condition there was that you had to start in Delaware.

Mechaniker

I previously published the shortest route solution, as well as the longest route solution, here ⬋

Interesting Map Problems — CS@CMU

littlemouse

I clicked and clicked on the arrow and nothing happened. :(

dadoctah

You see an arrow somewhere? 'Cause I don't.

littlemouse

⬋⬋⬋
Guess you need to update your browser, because as we know, that's the solution to everything on the internet. :)

dadoctah

I see three little boxes that say 2B in the upper half and 0B in the bottom.

You're not going to get many rabbits with arrows like that.