Question 4
Original English statement:
A number of robots are placed on the squares of a finite, rectangular grid of squares. A square can hold any number of robots. Every edge of the grid is classified as either *passable* or *impassable*. All edges on the boundary of the grid are *impassable*.
You can give any of the commands *up*, *down*, *left*, or *right*. All of the robots then simultaneously try to move in the specified direction. If the edge adjacent to a robot in that direction is passable, the robot moves across the edge and into the next square. Otherwise, the robot remains on its current square. You can then give another command of *up*, *down*, *left*, or *right*, then another, for as long as you want.
Suppose that for any individual robot, and any square on the grid, there is a finite sequence of commands that will move that robot to that square. Prove that you can also give a finite sequence of commands such that *all* of the robots end up on the same square at the same time.
Translation of the parallel French statement:
A number of robots are placed on the squares of a finite, rectangular grid of squares. A square can hold any number of robots. Every edge of the grid is classified as either *passable* or *impassable*. All edges on the boundary of the grid are *impassable*.
You can give any of the commands *up*, *down*, *left*, or *right*. All of the robots then simultaneously try to move in the specified direction. If the edge adjacent to a robot in that direction is passable, the robot moves across the edge and into the next square. Otherwise, the robot remains on its current square. You can then give another command of *up*, *down*, *left*, or *right*, then another, for as long as you want.
Suppose that for any individual robot, and any square on the grid, there is a finite sequence of commands that will move that robot to that square. Prove that you can also give a finite sequence of commands such that *all* of the robots end up on the same square at the same time.
A number of robots are placed on the squares of a finite, rectangular grid of squares. A square can hold any number of robots. Every edge of the grid is classified as either *passable* or *impassable*. All edges on the boundary of the grid are *impassable*.
You can give any of the commands *up*, *down*, *left*, or *right*. All of the robots then simultaneously try to move in the specified direction. If the edge adjacent to a robot in that direction is passable, the robot moves across the edge and into the next square. Otherwise, the robot remains on its current square. You can then give another command of *up*, *down*, *left*, or *right*, then another, for as long as you want.
Suppose that for any individual robot, and any square on the grid, there is a finite sequence of commands that will move that robot to that square. Prove that you can also give a finite sequence of commands such that *all* of the robots end up on the same square at the same time.
Translation of the parallel French statement:
A number of robots are placed on the squares of a finite, rectangular grid of squares. A square can hold any number of robots. Every edge of the grid is classified as either *passable* or *impassable*. All edges on the boundary of the grid are *impassable*.
You can give any of the commands *up*, *down*, *left*, or *right*. All of the robots then simultaneously try to move in the specified direction. If the edge adjacent to a robot in that direction is passable, the robot moves across the edge and into the next square. Otherwise, the robot remains on its current square. You can then give another command of *up*, *down*, *left*, or *right*, then another, for as long as you want.
Suppose that for any individual robot, and any square on the grid, there is a finite sequence of commands that will move that robot to that square. Prove that you can also give a finite sequence of commands such that *all* of the robots end up on the same square at the same time.