On Thu, Feb 18, 2010 at 8:11 AM, David Wilson <davidwwilson@comcast.net> wrote:
Let a building be constructed in the form of a finite undirected connected graph with no other special properties (e.g, not necessarily loopless or planar).
Each edge is a corridor, each vertex a circular room. Corridors enter at doors in fixed positions around the room, so that you can tell which corridor is left or right of another with respect to the vertex.
You are placed in a random corridor in this building. You are allowed to walk through the building under the restriction that you leave a room at a door left or right of the one which you entered. Rooms and corridors may be identical, so you cannot hope to recognize any room or corridor you have previously visited, nor are you allowed to mark rooms or corridors.
Your task is to visit every room in the building. Is there a fixed sequence of left-right choices that will allow you to do this, regardless of the building configuration?
Yes. Proof sketch: Lemma 1. For any such graph, and any starting location, there is a sequence of left-right choices that visits every room. (This was trickier than I would have thought to prove; in particular, it needs to make essential use of the finiteness of the graph). Lemma 2. For any such graph and any such starting point, the measure of the set of all infinite LR sequences that visit all rooms is 1. Since there are a countable number of (Graph, starting point) pairs, the measure of the set of all infinite LR sequences that visit all rooms in all finite connected graphs is 1. So not only does there exist such a sequence, you have to work hard (or be infinitely unlucky) to find a sequence which is *not* one of the ones you're looking for! This shows that there is a finite such sequence that works for any finite collection of graphs and starting points, such as the set of all graphs with less than N vertices. It seems like there should be a proof of this purely combinatorial fact that doesn't rely on infinite sequences and measure, but finding one is annoyingly difficult. Andy