Library / /9 of 17

, 2012

Combinatorics Difficulty 6.3 National olympiad Prove it Canada

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.

Un certain nombre de robots sont placés sur les carrés composant une grille rectangulaire de dimension finie. Chaque carré peut contenir un nombre quelconque de robots. Les bords des carrés de la grille sont classés comme franchissable ou infranchissable. Les côtés qui forment le pourtour de la grille sont infranchissables.
Vous pouvez donner n'importe laquelle des commandes suivantes : en haut, en bas, à gauche ou à droite. Tous les robots tentent alors de se déplacer simultanément dans la direction précisée. Si le bord adjacent au carré vers lequel se déplace un robot est franchissable, le robot le franchit et se place dans le carré suivant. Sinon, le robot reste dans le carré où il se trouve. Vous pouvez ensuite lancer une autre commande de déplacement vers le haut, le bas, la gauche ou la droite, et encore une autre, aussi longtemps que vous le désirez.
Supposons que pour chaque robot, et ce, pour n'importe quel carré, il existe une suite finie de commandes qui amèneront ce robot au carré donné. Démontrez que vous pouvez aussi lancer une suite finie de commandes de sorte que tous les robots finiront par se retrouver simultanément dans le même carré.

Solution

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 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 = \{s_1, s_2, \dots, s_n\}$ 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}, \dots, s_n$ and then to the square where $B$ is currently with the commands $s_1, s_2, \dots, 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 + kv$ and $B$ to $B + kv$ . But if $v \neq (0,0)$ , this will eventually force $B$ off the edge of the grid, giving a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.