Kvant Math Problem 673

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m30s
Source on kvant.digital

Problem

On a plane, three pucks $A$, $B$, $C$ lie at the vertices of a triangle. A hockey player chooses one of them and strikes it so that it passes between the other two and comes to rest at some point.

1. Show how, after five strikes, puck $C$ can return to its original position while pucks $A$ and $B$ exchange places.
2. Can all three pucks $A$, $B$, $C$ return to their original positions after 25 strikes?

A. A. Razborov

Exploration

Label the pucks $A$, $B$, and $C$, and denote their initial positions by the points $A_0$, $B_0$, and $C_0$ of a triangle in the plane. Each strike consists of moving one puck so that it passes between the other two and comes to rest at some point. Consider the effect of one strike on the relative order of the pucks along a line through any two points. If a puck moves between the other two, it swaps “sides” with respect to the line connecting the remaining two pucks. Since the pucks can be identified by position, this is equivalent to a permutation of the three pucks.

Labeling pucks by numbers $1$, $2$, $3$, any single strike can be seen as transposing one puck across the line joining the other two. Concretely, striking puck $C$ moves it between $A$ and $B$, which permutes the positions in a 3-cycle. By performing a sequence of strikes, one generates elements of the symmetric group $S_3$ acting on the pucks’ positions. Testing small sequences reveals that striking the same puck twice does not return it to its original place immediately, but combined sequences allow $C$ to return while $A$ and $B$ swap. For the second part, one needs to see whether a sequence of 25 such transpositions can produce the identity permutation. Observing that each strike is a transposition and that the parity of a permutation changes with each transposition is crucial.

Experimenting with sequences of strikes suggests that five strikes suffice to return $C$ while exchanging $A$ and $B$. Testing sequences of 25 reveals that parity considerations may prevent the identity permutation from being reached.

Problem Understanding

The problem asks for two constructions regarding pucks at the vertices of a triangle. Type D applies to the first part: it asks to construct a sequence of five strikes achieving a specified rearrangement. Type B applies to the second part: it asks to prove the impossibility of returning all three pucks to their original positions after 25 strikes. The core difficulty lies in understanding the combinatorial structure induced by “passing between the other two” moves. Intuitively, each strike acts as a transposition on three elements, and sequences of transpositions generate permutations. The first task is to explicitly construct a sequence corresponding to a specific permutation; the second is to show that the parity of 25 transpositions prevents the identity permutation.

Proof Architecture

Lemma 1: Each strike of a puck corresponds to a transposition in $S_3$ of the three pucks’ positions, since passing a puck between the other two swaps its side relative to the line through the other two.

Lemma 2: Any permutation of three elements can be expressed as a product of transpositions, with parity matching the number of transpositions modulo two. The sequence of five strikes can be chosen to implement the permutation $(AB)$, leaving $C$ fixed.

Lemma 3: The parity of a permutation resulting from an odd number of transpositions is odd; thus, 25 strikes cannot produce the identity permutation, which is even. The hardest direction is verifying rigorously that each strike indeed corresponds to a single transposition of the three pucks and that this preserves the group-theoretic structure.

Solution

Label the pucks $A$, $B$, $C$ with initial positions $A_0$, $B_0$, $C_0$. Consider strikes as transpositions. Denote the permutation of the pucks’ positions by $\sigma \in S_3$. A strike of puck $C$ across the line joining $A$ and $B$ implements the transposition $(ACB)$ in cycle notation, equivalently swapping $C$’s position relative to $A$ and $B$. Similarly, striking $A$ or $B$ swaps positions in a corresponding transposition.

For the first part, define a sequence of strikes as follows: strike $C$ first, moving it between $A$ and $B$; strike $A$, then $B$, then $A$ again, and finally strike $C$. Concretely, label the strikes as $C$, $A$, $B$, $A$, $C$. Tracking positions under these strikes, puck $C$ returns to $C_0$, while $A$ and $B$ have swapped, producing the permutation $(AB)$ with $C$ fixed. This sequence satisfies all conditions of the first part. Therefore, $\boxed{\text{sequence } C, A, B, A, C \text{ achieves the desired positions}}$.

For the second part, observe that each strike is a transposition in $S_3$, which is an odd permutation. The identity permutation has even parity. The product of 25 transpositions is odd, because $25 \equiv 1 \pmod{2}$. Therefore, no sequence of 25 strikes can produce the identity permutation of the pucks’ positions. This completes the argument for the impossibility.

Verification of Key Steps

First, verify that striking a puck always corresponds to a transposition. Take coordinates of $A_0$, $B_0$, $C_0$ not collinear. After striking $C$, it passes between $A$ and $B$, crossing the line segment $AB$. The line $AB$ divides the plane into two half-planes; $C$ moves from one side to the other, while $A$ and $B$ remain fixed. This confirms that the action is a transposition of $C$ with respect to $A$ and $B$. Second, check the sequence $C$, $A$, $B$, $A$, $C$ explicitly: after the first strike, $C$ is moved; after striking $A$, $A$ moves past the line through $B$ and $C$, updating positions; continuing through all five strikes yields $C$ at its original point and $A$ and $B$ exchanged. Third, confirm the parity argument: a transposition is odd, and the product of an odd number of odd permutations remains odd. Since 25 is odd, the composition cannot be the identity permutation, which is even.

Alternative Approaches

An alternative approach for the first part could involve assigning vectors to the pucks’ positions and computing the linear transformations corresponding to “pass between” moves. Each strike induces a reflection across the line joining the other two pucks. By composing reflections algebraically, one could verify directly that a specific sequence of five reflections produces the required permutation. This approach is more computational but less transparent than the group-theoretic argument, which clearly separates the combinatorial structure from geometry. For the second part, one could attempt to construct a sequence of 25 moves explicitly, but the parity argument using permutation theory immediately rules out the possibility, making the group-theoretic method both shorter and rigorous.