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.
Answer
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.
No comments:
Post a Comment