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?

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 tha…

"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?

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 app…

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 …

@ 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, …

@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 uniq…

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.

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 eithe…

mouse — "I'll be too busy looking good."If you say so — post a pic and let us decide.

dadoctah</B — "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.

The Traveling Salesman Problem (greatly simplified)

The Show

Mechaniker February 24, 2012, 3:54am 13

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

Interesting Map Problems — CS@CMU

Topic		Replies	Views
$1M Prize for Solution of Traveling Salesman Problem The Show	9	12924	September 20, 2021
Geographic Oddity Puzzler Answer The Show plymouth	41	3737	June 21, 2010
US city The Show	24	1777	May 27, 2010
Favorite road trip destinations General Discussion	58	1894	September 16, 2017
Winter driving trouble, Google Maps Fail! General Discussion	36	2742	January 8, 2022

The Traveling Salesman Problem (greatly simplified)

Related topics