10
$\begingroup$

Wanda the Wanderer is driving the streets of Gnu York. She doesn't know the what the entire map of Gnu York looks like, but she knows this much:

  • Gnu York is flat
  • Every intersection of streets is four-way, resembling a "+"
  • There are no overpasses, tunnels, or dead ends
  • There are no streets leading out of Gnu York
  • There are only finitely many intersections

Whenever Wanda reaches an intersection, she decides whether to go left, right or straight according to the repeating pattern

Left $\to$ Right $\to$ Straight $\to$ Left $\to$ Right $\to$ Straight $\to\dots$

So, if she turned left before, she will turn right at the next intersection, then go straight at the one after that, then left at the one after that.

At noon, Wanda passes by city hall. Prove that she will eventually pass by city hall again.

Below is a an example of what Gnu York might look like, with $\color{red}{\star}$ being city hall, along with how Wanda's path would start out. However, your proof should work for any road layout which obeys the given rules, not just the one below.

Gnu York

$\endgroup$
  • 3
    $\begingroup$ Do you want to add the condition that there is no way to drive in or out of Gnu York? Otherwise, a trivial map (say, with a single intersection +and the roads extending west to Filladelphia and south to Phlorida) shows she will not pass city hall again. $\endgroup$ – user1717828 Sep 18 '15 at 20:43
13
$\begingroup$

There are a finite number of states she can be in, where a state is determined by direction, road, and upcoming turn. Each state has a unique predecessor and successor; therefore, there are no branches in the directed graph of states as vertices and edges connecting each state to its successor. This means every state must be part of a cycle.

$\endgroup$
  • 3
    $\begingroup$ No branches, whether you're going backwards or forwards, and finite number of states. Great solution. $\endgroup$ – Dr Xorile Sep 18 '15 at 21:39
0
$\begingroup$

There's only two possibilities for such movement.

Option one is that Wanda never hits an end of the path, going on left-right-straight (which is impossible, because it's countered by the requirement that the number of intersections is finite).

Option two is that she at some point hits a straight that she's already been on. If it's arrived to and passed along on in opposite direction, then every left turn has a corresponding right turn when she was there the last time. It means that she's bound to arrive at the point of origin, hence undoubtedly passing the city hall again.

Now, is it possible to get to the same street in the same direction without traveling back along it first? No, because that would contradict the patter of left turn being a right turn when traveling back. Once she's hitting any street she's been on (as shown in the first paragraph), she's unable to follow other path than the one she's been on (but in the opposite direction).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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