8
$\begingroup$

I'm posting this from my phone again because I've gotten hopelessly lost in Boston, really want to go home, and desperately need the help of some clever people on the internet. Please help me - I'm really lost and I would like to, after some finite amount of driving, get back home and I don't know any better way to do that than to ask about my problem on a puzzling site.

I'm not very good at remembering things, so any approach based on recalling whether I've been at a location before isn't going to work. However, I'm really good at following directions, so what I'd really like is to be given a list of numbers. Each time I reach an intersection, I'll read the next number, count that many turns from the right, and follow that road - so at a standard* 4 way intersection, a $1$ will tell me to turn right, a $2$ to go straight, a $3$ to turn left and a $4$ to make a U-turn (and a $5$ brings me back to turning right and so on). I define an intersection as any moment at which I have an opportunity to turn (so if a street branches off from the one I'm on, that's a 3-way intersection).

From my extensive experience as a driver, I have observed the following: there are only finitely many intersections and that, at each, only finitely many roads meet. Also, I'm quite sure that it is possible to get back to my house from any point in the road network (Boston's not that bad**). Finally - and I'm quite proud of this - if I drive by my house (which is located by a road), I will definitely recognize it.

Can any of you suggest a sequence$^{***}$of instructions that will get me home?


(*Of course, Boston's road network is so messed up that there are approximately zero standard intersections. This doesn't affect the answer though.)

(**For the purposes of this question.)

(***Given that I do not know how many roads there are in this city, this sequence is necessarily infinite. Please do not try to write an entire infinite sequence in your answer - a mathematical construction is expected instead).

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of puzzling.stackexchange.com/questions/22373 ? $\endgroup$ – GentlePurpleRain Nov 25 '15 at 17:38
  • $\begingroup$ are we to assume all intersections are standard? if not, define intersection - if I drive past an opportunity to turn right (where left is not an option), was that an intersection? If my next number is 1, should I have turned right at it? $\endgroup$ – Kate Gregory Nov 25 '15 at 17:53
  • $\begingroup$ 1. Become cyborg 2. Hack CIA to acquire map 3. Apply Dijkstra's path finding algorithm 4. Teleport to home 5. Fool CIA because they think you are still in Boston 6. $ \operatorname{Profit} $ $\endgroup$ – AvZ Nov 25 '15 at 18:34
  • 3
    $\begingroup$ @GentlePurpleRain: It's not a dupe. The other one started with a specific sequence of turns and the knowledge that you passed a building, asking whether you would pass it again. In addition, it guaranteed that all intersections were 4-way. They're entirely different. $\endgroup$ – Deusovi Nov 25 '15 at 20:27
  • 2
    $\begingroup$ @GentlePurpleRain I did see that question before I posted this one, but there's nothing beyond superficial similarity (i.e. that they're both graph theory based); there, you are given a sequence and asked about the result. Here, there is an intended result, and you are asked for a sequence. The answers are totally different. $\endgroup$ – Milo Brandt Nov 25 '15 at 20:55
6
$\begingroup$

For any number $n$, there are finitely many connected graphs with $n$ edges. So we can make lists of all the graphs with no edges, all the graphs with one edge, all the graphs with two edges, and so on. If we join these lists together, we can make an infinite list that is guaranteed to contain every finite graph.

Now, for each graph, there are finitely many ways to choose a starting point, ending point, and starting direction, so we can make a list of every possible starting situation.

Once we have this list, assume that we started in the first situation on the list, and try to get to the target based on that. If that doesn't work, we assume that we started in the second situation and figure out where we ended up. Then, we go to the target from there. If we still aren't done, we keep continuing down the list in the same way.

Because the list contains every possible starting situation, eventually we will reach the right one, at which point we will arrive at the target.

$\endgroup$
  • $\begingroup$ Might take a while, though. Better pack a lunch. $\endgroup$ – Michael Seifert Sep 15 '16 at 16:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.