I just started reading The English Major by Jim Harrison. It’s about Cliff, a retired high school teacher and farmer, whose wife has just left him. He decides to travel to the lower 48 states in the US using a puzzle as a guide.
He starts in Michigan, then goes to Wisconsin, and in Minnesota he hooks up with a former student of his, Marybelle,who decides to ride with him through North Dakota to Montana. At this point Cliff relates:
After breakfast in Wahpeton and before she fell asleep Marybelle had said it would be nice to do some north and south zigzagging on the way to Bozeman. I didn’t say anything but this distressed me as I had intended to enter and exit each state exactly once.
When I read this, I was immediately distracted by the question of whether or not that was even possible.
As a follow up question, if Cliff had started anywhere he wanted instead of his hometown, how close could he end to where he started?
For reference here’s a map of the United States, with Hawai‘i and Alaska conveniently resized and located in Mexico. Click for a bigger version.
360 
April 22, 2009 at 8:42 pm |
Without cheating and looking up some graph theory, I see an immediate problem in New England. Let’s say you don’t start in Maine, so you have to get in and out, so you go: NH ME NH but you have to get out of NH again, so you would have to exit it twice.
If you start in Maine, then I don’t see a way to visit both VT and RI while entering/exiting each exactly once.
April 22, 2009 at 9:40 pm |
If he has to end up back in Michigan, it’s not possible unless he can go into Canada. That’s easy to see because New England is like Australia in the game Risk: there’s only one way to enter it, and that’s through New York. Further, Maine is also cut off, only accessible through New Hampshire.
The rest of the country is no trouble. Continuing from where he’s already been, he can do, for example, MI, WI, MN, ND, SD, MT, WY, ID, WA, OR, CA, NV, UT, AZ, NM, CO, NE, KS, OK, TX, LA, AR, MO, IO, IL, IN, OH, WV, KY, TN, MS, AL, FL, GA, SC, NC, VA, MD, DE, PA, NJ, NY, CT, RI, MA, VT, NH, ME
He can then return from ME to MI through Canada, if he allows himself that. If not, well, Maine is a very nice place to move to, especially if you’re from Michigan.
But no matter where he starts, the closest he can hope to get to closing the loop without including Canada is by starting in Maine and ending in Pennsylvania or New Jersey (or the other way ’round).
April 22, 2009 at 9:43 pm |
It is possible to do that. Here’s one solution. Note that since Maine only borders one other state, all such tours have to start or end in Maine.
April 22, 2009 at 9:45 pm |
I did not notice that NY bordered CT. I’m a dumbass.
And also, that Google Map is nice work.
April 23, 2009 at 6:41 am |
Neat map Michael!
I initially thought it was impossible, but then realized that I was thinking of it as an Eulerian path [which would actually correspond to crossing each border exactly once], and it’s really Hamiltonian.
Then I realized it was possible, but I thought starting in Michigan was problematic. It took me a while to realize that he could just end up in Maine. I’m not much further in the book, so maybe that’s what happens!
April 23, 2009 at 7:01 am |
I was thinking Eulerian as well when I first saw the problem. I’d also be shocked to discover that the US has a Eulerian path. A “random” planar graph almost certainly doesn’t have a Eulerian path — the restriction on the degrees is just too restrictive.
April 23, 2009 at 10:10 am |
Is he going to hit Alaska and Hawaii? He could start in Michigan, drive the western half of Michael’s route and then up to Alaska. From there, he flies to Hawaii, from Hawaii to Maine, and then drives the eastern half of the route, ending up back home.