On the suddenly hot topic of the Traveling Salesman Problem (see here and here), this week’s Car Talk puzzle is a TSP-like problem (though it is really a graph theory problem: the hamiltonian path problem to be exact).
The company that Bobo works for just finished a new product. They wanted to promote it across the country. Bobo was asked to travel by car to each of the 48 contiguous U.S. states to promote the product. He was told that he could visit each state in whatever order he chose, but the company wanted him to start in Delaware, at their headquarters.
They asked that he visit each state only once. He could not go back into a state he had already visited because this was the “Don’t Look Back” product tour. So, Bobo sat down at his desk and began to plan his trip.
He realized immediately that it was going to be one long car trip. At that moment, his boss stopped by and said, “Hey, I’m going to join you when you reach your last state. I was born there and I’ve been looking for a reason to go back and visit. You can leave your rental car there, and I’ll fly you back in my private jet.”
Since Bobo hadn’t planned his trip yet, how did his boss know which state was going to be Bobo’s last state? And, which state would that be?
That question is not hard (I won’t ruin it by giving the solution here: call the state X); the key is the statement about the flight back from the final state.
But it is strange that Delaware was given as the starting state. Does it really matter? Well, if you start in State X, you can end up in many (but not all) of the other states. But it if you start in some other states, there is no path through all the other states without repeating a state. I count seven starting states that preclude paths through all the other states by road without repeating a state. Which can you find? The following map is just for illustrative purposes: the question refers to the “real” United States state structure (so you might need to check a more detailed map to see what states connect directly to others).
NOTE ADDED 1/17/2012. Reddit’s lordlicorice has drawn the graph underlying the States:
Thanks to @wjcook for pointing out the Car Talk problem.
I think I’ve found both the answer, and the seven states .. ! Won’t share them though .. !
Well, Matt Saltzman sent me the right answer, but no other takers? Too easy perhaps?
…isn’t it Maine? The only to get there is through New Hampshire, and given the stipulation of the “Don’t Look Back” product tour, you wouldn’t be able to leave once you’re there. [OK, that is State X: now how about the more interesting question of which states can’t you start in? MT]
The car talk puzzler answer is out, and state X is, of course, Maine. http://www.cartalk.com/content/bobos-dont-look-back-tour-0?answer
If you would like to know the answer to the “which states can’t you start in, here is the encoded answer (kids, look up ROT13 if you can’t guess the code):
Vs lbh qba’g fgneg va Znvar, lbh unir gb raq va Znvar. Arj Lbex phgf bss gur abegurnfg, fb nal fgngr abegurnfg bs Arj Lbex (vapyhqvat Arj Lbex ohg abg Znvar), unf n ceboyrz: lbh pna’g rkvg gur abegurnfg naq gura erghea gb svavfu ng Znvar. Ab abar bs PG, EV, AL, ZN, AU, be IG pna or gur fgnegvat fgngr.
Gur friragu fgngr: Trbetvn! Vs lbh fgneg va Trbetvn, lbh jvyy eha vagb gebhoyr bapr lbh ivfvg SY be FP hayrff lbh ivfvg gubfr fgngrf svefg. Lbh pna bayl ivfvg bar fgngr svefg, fb lbh jvyy trg fghpx ng rvgure SY be FP.
Gur erfg bs gur fgngrf ner yrtvgvzngr fgnegvat fgngrf.