9
$\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).

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Possible duplicate of puzzling.stackexchange.com/questions/22373 ? $\endgroup$ Commented Nov 25, 2015 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$ Commented Nov 25, 2015 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$ Commented Nov 25, 2015 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$ Commented Nov 25, 2015 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$ Commented Nov 25, 2015 at 20:55

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Might take a while, though. Better pack a lunch. $\endgroup$ Commented Sep 15, 2016 at 16:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.