A tourist in Moscow

[BMAD]

The tourist has come to the Moscow by train. All-day-long he wandered randomly through the streets. Than he had a supper in the cafe on the square and decided to return to the station only through the streets that he has passed an odd number of times. 

 

Prove that he is always able to do that.

[k-man]

The approach of the proof is to shorten the entire path that the tourist took by eliminating any streets that were passed an even number of times and showing that the resulting path is still connecting the station and the cafe. Any even number of passes through a street can be looked at in pairs as they happened sequentially (the first pass with second, the third with the fourth, etc.). Each pair of passes is done either in the same direction or in the opposite directions.

 

If a tourist passed through a street and later passed it again in the opposite direction, he completed a cycle and returned to a previously visited point. The entire section of the path between and including these 2 passes can be removed from the path without breaking it. After eliminating all such cycles from the tourist's path we are left with a shorter path still connecting the station and the cafe, but now all the remaining pairs when the same street was passed are now in the same direction. Let's look at one such pair for street X. A tourist passed the street X twice in the same direction. That means he came to the beginning of the street (let's call it point A), passed the street the first time to the end (point B) and then took some path connecting B->A without passing through X. After that he passed through X the second time ending again at point B. So, there is a part of the tourist's path that connects A to B and excludes street X. We can eliminate both passes of street X while still having points A and B connected. We can eliminate all pairs in the same way while preserving the connection between the station and the cafe. The resulting path will only include the streets that the tourist visited an odd number of times.

 

Note that when reversing the path from B->A to be traveled A->B, it's possible that some remaining pairs become traveled in the opposite directions rather than in the same direction. This is not a problem as we can eliminate both types of pairs without breaking the path.

[bonanova]

[spoiler='Related problem - labyrinth']The classical solution for the garden variety labyrinth, that has high hedges that offers no view from above, is to keep your right shoulder in contact with the hedge. That has the effect of sending you down roughly half of the dead ends, (you do the other dead ends with your left shoulder) and returning from them, thus labeling every dead-end path as having been traversed twice, and avoiding all circular paths. 

 

Every labyrinth is isomorphic with a straight path from entrance to exit, with spurious side paths that are either circular or have dead ends. As k-man observes, these can all be deleted without severing the tourist's path to his destination. Thus, when the exit is reached, every spurious path will have been traversed twice while the direct entrance-to-exit path will have been traversed only once.

 

This puzzle translates to having the train station at the entrance to a maze and the restaurant at its exit. The fact that a maze has dead ends that don't exist in Moscow does not change this fact. One can simply create a maze that conforms to the tourist's path, placing dead ends wherever the tourist decided to turn around. Upon return, the tourist simply follows the once-trod straight path.

[k-man]

[spoiler='Related problem - labyrinth']The classical solution for the garden variety labyrinth, that has high hedges that offers no view from above, is to keep your right shoulder in contact with the hedge. That has the effect of sending you down roughly half of the dead ends, (you do the other dead ends with your left shoulder) and returning from them, thus labeling every dead-end path as having been traversed twice, and avoiding all circular paths. 

 

Every labyrinth is isomorphic with a straight path from entrance to exit, with spurious side paths that are either circular or have dead ends. As k-man observes, these can all be deleted without severing the tourist's path to his destination. Thus, when the exit is reached, every spurious path will have been traversed twice while the direct entrance-to-exit path will have been traversed only once.

 

This puzzle translates to having the train station at the entrance to a maze and the restaurant at its exit. The fact that a maze has dead ends that don't exist in Moscow does not change this fact. One can simply create a maze that conforms to the tourist's path, placing dead ends wherever the tourist decided to turn around. Upon return, the tourist simply follows the once-trod straight path.

 

Interesting analogy, but I'm not convinced it applies here.

The tourist didn't necessarily follow the "right hand rule", so defining the maze that conforms to the tourist's path and choosing the straight path may still result in using the streets that were traveled twice.

 

Here is a simple example. Letters are points on a directional graph defining the path. A = train station, E = cafe.

 

Path: A->B, B->C, C->D, D->B, B->C, C->E

 

Street B->C was traveled twice, but would be part of the straight path returning from E to A (E->C->B->A) if you were to use right (or left) hand rule. The sought path would be E->C->D->B->A.

[bonanova]

Oh, the right- or left- shoulder "rule" only guarantees that you will find the exit of a maze.

 

The path from entrance to exit divides the maze into two disjoint sets of barriers.

Your shoulder will follow the inner surface of one of sets until the exit is reached.

If you continue, you will trace the outer surface of the barriers (hedges), and return

(by another route) to the entrance.

 

I'm not sure what my points was, actually, except that there is a route from start to finish

that demonstratively will have (only) odd visits, and the same is true of a maze -- not

necessarily because it is true of a maze. I may have overstated the importance of that

similarity -- I didn't give it that much thought -- although similar observations do apply

to both cases.

[gavinksong]

I just found this thread, and I think I can come up with a simpler proof.

Of the roads at every juncture, there is an even number of roads that the tourist has passed an odd number of times - except at the cafe and the station. Thus, when the tourist enters a junction through an odd-travelled road, there is always another odd-travelled road that he can leave by. This also holds while he is making his way back to the station. Since there is a finite number of odd-travelled roads, the tourist must eventually reach a dead-end, and when he does, he must be at the station.

[BMAD]

well done.