Tuesday 15 September 2015

graph theory - Lost in Gnu York


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



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

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...