48 state tour (answer by Joseph DeVincentis)
There's no way around NY, so you must do the 6 states east of it first, and
MA splits those into two groups as well. RI must be between MA and CT, and
NH must be 2nd, so you must start ME-NH-MA-RI-CT-MA-NY.
There are a few other places where a state is only adjacent to two states,
so you must travel through the three states in order (or reverse order).
Georgia is adjacent to two such states!
The above works out to be the required order, because to do then in the
opposite order forces the path to intersect itself, and requires visiting a
state twice, since the State graph is planar, with one possible exception if
you're allowed to jump the corner at the Four Corners (I'll assume this is
More such segments will appear after some paths have been eliminated.
We visited New York 7th, but we can't get to Maryland until 16th, so we have
to visit several other states first. Pennsylvania and Maryland cut off New
Jersey and Delaware from the other states, and since we can't visit Maryland
yet, we must visit New Jersey and Delaware before passing through
Pennsylvania or we'll never get them. So the path continues: NY-NJ-DE-PA,
and then on to Ohio or West Virginia.
This leaves Maryland with only two ways in/out, Virginia and West Virginia,
so we also have a path segment WV-MD-VA, and from Pennsylvania you must go
The only remaining way to get to West Virginia is through Kentucky. Then you
need to visit two states between Ohio (11th) and Kentucky (14th), which can
only be MI-IN or IN-IL. IN-IL leaves Michigan with only one connecting
state, so we must choose MI-IN (and avoid the question of whether it's
permitted to hop between the two parts of Michigan.)
>From Virginia, you can either go straight to North Carolina (and from there
on around the coast to Alabama) or you can go to Tennessee first, then to
North Carolina etc.
This gives us the path:
>From Alabama you can go either to Mississippi or to Tennessee if you didn't
go there already. Now, we have to focus on getting to Washington by state
number 31. We can't just shortcut across the middle of the country, because
we'll cut off states that we can't get back to without crossing our path and
reusing a state.
If we visited Tennessee early, then Mississippi is the 24th state, and you
have to go through AR-MO-IL-WI-MN-ND-MT-ID to get to Washington without
cutting off any states, and that's too many. So we go straight from
Virginia to North Carolina earlier in the path, and then from Alabama to
Tennessee. From Tennessee you can then go through
MO-IL-WI-MN-ND-MT-ID-WA-OR to visit Washington on schedule.
>From Oregon, you can't go to California yet; CA must be last. So you must
from Oregon to Nevada, and you enter California from Arizona. From Nevada,
you can't go to California or Arizona for the same reason, so you must go to
Out of the states not yet visited, Iowa is only adjacent to South Dakota and
Nebraska, so that must be a part of the sequence. Utah is 34th, and Kansas
must be 39th, and the only way to get there using 4 states in between,
without cutting off any states, is WY-SD-IA-NE.
If we don't go to Colorado next, it will only be connected to New Mexico, so
we go to Colorado before taking the forced route to Mississippi and then
back across the states along the southern edge of the US.
Solution by Don Woods.
I read MathPuzzles only sporadically,
but a friend pointed me at this week's item since he knew
I'd be intrigued. My thesis topic was on the layout of
planar graphs, and one of my principal test cases was the
"adjacency graph" of the continental United States. So in
examining Friedman's puzzle I had the advantage of having
a convenient picture of the graph to work with, by copying
a page out of my thesis. ("Drawing Planar Graphs", Stanford
University, 1981. Available at contentville.com. :-)
Given the graph, the problem was not too difficult. The main
observation is that, because the graph is planar, the path
cannot cross itself. Thus when the time came to make a mad
dash from Alabama (#22) to reach Washington (#31) I knew I
had to hug the edge of the as-yet-unused portion of the
graph, leading to a unique path. The other general guide, of
course, was that once I had entered and left any state I
could remove from the graph all other connections to that
state, which often left unique paths through other states,
with cascading effects.
The resulting path is shown in the attached gif file. The
graph does not especially resemble the map, because my thesis
involved attempting to minimise the total length of the edges
(while constraining the edges' endpoints to have integer
As to the secondary problem, obviously Maine need not be
included among the restrictions, as it must be either first
or last and the other restrictions will determine which.
Each of the MD, WA, KS constraints did seem to be necessary,
though of course there might be other choices such that two
states could provide the same constraints. Putting CA as
#48 mainly served to define which boundary of the map was to
be followed while travelling from AL to WA, but for that
reason it too added useful information. Thus 4 states does
feel like a reasonable lower bound, but I have no proof.
I wonder how difficult it would be to write a program to
solve this sort of problem, so that one could try it with
each possible set of 3-state constraints to see if any of
them leads to a unique path? The Hamiltonian Path problem
is, of course, NP-complete, but for any given set of data
the solving time is obviously bounded, so it is certainly
possible that the puzzle could be analysed computationally.