Question 103
The main building of ETH Zurich is a rectangle divided into unit squares. Every side of a square is a wall, and some walls have doors. The outer wall of the main building has no doors. A number of SMO participants have got lost in the main building. They can only move from one square to another through doors. We assume that between any two squares of the main building there is a walkable path.
Cyril wants the participants to find each other again by leading all of them to the same square. To do this he can give them the following instructions by walkie-talkie: North, East, South or West. After each instruction, every participant simultaneously tries to walk one square in this direction. If there is no door in the corresponding wall, he stays where he is.
Show that Cyril can achieve his goal after finitely many instructions, no matter on which squares the participants are at the beginning.
Cyril wants the participants to find each other again by leading all of them to the same square. To do this he can give them the following instructions by walkie-talkie: North, East, South or West. After each instruction, every participant simultaneously tries to walk one square in this direction. If there is no door in the corresponding wall, he stays where he is.
Show that Cyril can achieve his goal after finitely many instructions, no matter on which squares the participants are at the beginning.