Rioplatense Mathematical Olympiad

Let us interpret the problem in terms of graphs. We can think of the initial configuration as a graph $G$ whose vertices are the platforms and whose edges are the bridges. This graph is connected. The claim is, then, that $G$ can be converted into another graph $G^{\prime }$ by rotating edges as in the statement if $G^{\prime }$ is connected and has the same number of vertices and edges as $G$. To prove this we will build a normal form of the graph in several steps. Note that, as the operations are invertible, the claim will be proved if this normal form depends only on the number of edges and vertices. We label the vertices of $G$ as $v_1,\dots ,v_n$, and suppose $G$ has $m$ edges.

STEP 1: Make $v_1$ have degree $n-1$. Assume that $v_1$ is not a neighbor of $v_i$. Since the graph is connected, there is a path connecting $v_1$ to $v_i$, i.e, there exists a sequence of vertices $w_0,w_1,\dots ,w_k$ such that $w_0=v_1$, $w_k=v_i$, and $w_j,w_{j+1}$ are connected by an edge for all $0\le j\le k-1$. Let's take one such path with $k$ minimal. By our initial assumption we have $k\ge 2$. Moreover, by minimality, $v_1$ is not connected to $w_j$ for any $j>1$. Therefore, we can apply the operation to $A=w_1,B=w_2$ and $C=v_1$. In this way, we get a shorter path connecting $v_1$ to $v_i$ without disconnecting $v_1$. By iterating this procedure we reach a situation in which $v_i$ is a neighbor of $v_1$, without removing any edges from $v_1$. So in the end $v_1$ will be connected by an edge to all $v_i$, and thus its degree will be $n-1$.

We will refer to this sequence of moves as $(\star )$.

Let $G_1$ be the graph obtained after Step 1, and $H_1$ be the graph obtained by removing vertex $v_1$ (with all its incident edges) from $G_1$. Let $C$ be the connected component of $v_2$ in $H_1$. Finally, let $m^{\prime }=m-(n-1)$ be the number of edges of $H$, and $N:=\min \{m^{\prime }+1,n-1\}$.

STEP 2: Make the size of $C$ equal to $N$. If $H$ is connected, then $C=H$ which has size $n-1$. We also have $m^{\prime }\ge n-2$, so $N=n-1$, and there is nothing to do. If there is an edge between two vertices $v_i$ and $v_j$ that are not in the same connected component as $v_2$, we can use $(\star )$ to rotate edge $v_i{v}_j$ into $v_i{v}_2$, so now $v_i$ is in $C$ as well. We iterate this until it is no longer possible. This is because either $H$ is now connected (and we are done), or because all other connected components have size 1 (isolated vertices). In the latter case, observe that now all the $m^{\prime }$ edges are in $C$, which is connected, so $C$ has at most $m^{\prime }+1$ vertices. If there are exactly $m^{\prime }+1$ vertices, we are done. Otherwise, since the number of edges is greater than or equal to the number of vertices, there is at least one edge $v_i{v}_j$ that can be removed without disconnecting $C$. So, if there is an isolated vertex $v_k$, using $(\star )$ we can rotate $v_i{v}_j$ into $v_i{v}_k$, which adds $v_k$ to $C$. We can keep doing this until either $C=H$ or we run out of edges, i.e., the size of $C$ is $m^{\prime }+1$.

STEP 3: Make $v_2$ connected to $v_3,\dots ,v_{N+1}$. First we proceed as in Step 1 to make sure that $v_2$ is connected to all vertices in $C$. If $C=\{v_2,v_3,\dots ,v_{N+1}\}$, we are done. Otherwise, there exist $3\le i\le N+1$ and $j>N+1$ such that $v_2{v}_j$ is an edge but $v_2{v}_i$ is not. So we can rotate $v_2{v}_j$ into $v_2{v}_i$, and iterate the process. After Step 3, we consider the subgraph $G_2$ whose vertices are $v_2,v_3,\dots ,v_{N+1}$. This graph is connected and, moreover, $v_2$ is connected to all other vertices, so we are in the same situation we were with $G_1$, and we can iterate Step 2 and Step 3. This goes on until we run out of edges, and we reach the normal form. Since $\mathrm{deg}(v_i)$ depends exclusively on $n$ and $m$ for all $i$, the problem is solved.