We will prove any two robots can be moved to the same square. From that point on, they will always be on the same square. We can then similarly move

## Sun Life Financial Canadian Mathematical Olympiad

!

a third robot onto the same square as these two, and then a fourth, and so on, until all robots are on the same square.

Towards that end, consider two robots $A$ and $B$. Let $d(A, B)$ denote the minimum number of commands that need to be given in order to move $A$ to the square on which $B$ is currently standing. We will give a procedure that is guaranteed to decrease $d(A, B)$. Since $d(A, B)$ is a non-negative integer, this procedure will eventually decrease $n$ to 0, which finishes the proof.

Let $n=d(A, B)$, and let $S=\left\{s_{1}, s_{2}, \ldots, s_{n}\right\}$ be a minimum sequence of moves that takes $A$ to the square where $B$ is currently standing. Certainly $A$ will not run into an impassable edge during this sequence, or we could get a shorter sequence by removing that command. Now suppose $B$ runs into an impassable edge after some command $s_{i}$. From that point, we can get $A$ to the square on which $B$ started with the commands $s_{i+1}, s_{i+2}, \ldots, s_{n}$ and then to the square where $B$ is currently with the commands $s_{1}, s_{2}, \ldots, s_{i-1}$. But this was only $n-1$ commands in total, and so we have decreased $d(A, B)$ as required.

Otherwise, we have given a sequence of $n$ commands to $A$ and $B$, and neither ran into an impassable edge during the execution of these commands. In particular, the vector $v$ connecting $A$ to $B$ on the grid must have never changed. We moved $A$ to the position $B=A+v$, and therefore we must have also moved $B$ to $B+v$. Repeating this process $k$ times, we will move $A$ to $A+k v$ and $B$ to $B+k v$. But if $v \neq(0,0)$, this will eventually force $B$ off the edge of the grid, giving a contradiction.

1. Induction Basis:
- We start by considering the case of two robots, $A$ and $B$, on a grid of height $m$ and width $n$.
- By the problem's assumption, there exists a finite sequence of commands that can move robot $A$ to the position of robot $B$. Let the length of this path be $\ell$.

2. Relative Positioning:
- Without loss of generality (WLOG), assume that robot $B$ is above robot $A$. This means that robot $B$ is either directly above or to the right of robot $A$.

3. Movement Analysis:
- When robot $A$ moves one square along the path towards $B$, two scenarios can occur:
- Scenario (i): Robot $B$ moves in the same direction as robot $A$. In this case, the path length $\ell$ remains constant because the distance decreased by one on $A$'s side and increased by one on $B$'s side.
- Scenario (ii): Robot $B$ cannot move in the same direction as $A$. In this case, the path length $\ell$ decreases because $A$ moves closer to $B$.

4. Path Traversal:
- Move robot $A$ to the original position of robot $B$ along the path. If at any point $A$ coincides with $B$, we have achieved our goal.
- If $A$ does not coincide with $B$, continue moving $A$ to $B$'s new position and repeat the process.

5. Contradiction Argument:
- Suppose, for the sake of contradiction (FTSOC), that scenario (ii) never occurs. This implies that both robots $A$ and $B$ are making the same moves, and $B$ is always above $A$.
- Consequently, every time $A$ moves to $B$'s previous location, both robots are moving upwards by at least one square.
- This leads to an absurd situation where $B$ would move upwards by $m$ squares, which is impossible since the grid has height $m$ and $B$ cannot start from the bottom row.

6. Conclusion:
- Therefore, scenario (ii) must occur at least once, causing the path length $\ell$ to decrease.
- By repeating the process described in steps 3 and 4, the path length $\ell$ will eventually reduce to zero, meaning that robots $A$ and $B$ will coincide.

7. Induction Step:
- By induction, if we can bring two robots to the same square, we can extend this argument to any number of robots by iteratively applying the same process to pairs of robots.

$\blacksquare$