An Adaptation Of A British Math Olympiad Problem
This problem, adapted from a British Mathematical Olympiad, is a real tricky one. Requires a higher order of thinking to be able to solve.
Problem contributed by debosmita1729
-----------book page break-----------
We denote the sequence of numbers on the blackboard by $A = (a_1, a_2, \dots, a_n)$. It is sufficient to analyze the sequence of residues modulo $3$, denoted by $R = (r_1, r_2, \dots, r_n)$ where $r_i \equiv a_i \pmod 3$.
Let us examine the effect of the allowed moves on the residue sequence $R$.
Effect of Move (i): This move acts on a triplet $(x, y, z)$ where $x+y+z \equiv 0 \pmod 3$. This condition implies that the residues $\{r_x, r_y, r_z\}$ are either a permutation of $\{0, 1, 2\}$ or are all equal. If the residues are equal, the sequence $R$ remains unchanged. If the residues are distinct (a permutation of $\{0, 1, 2\}$), the move performs a cyclic shift on these three adjacent residues. For instance, $(1, 2, 0) \to (2, 0, 1)$.
Effect of Move (ii): This move swaps adjacent $x, y$ only if $x \equiv y \pmod 3$. Since $r_x = r_y$, swapping them does not change the residue sequence $R$. However, it allows us to arbitrarily reorder the actual integer values within any specific residue class.
Conclusion: We only need to determine if the residue sequence of the initial state can be transformed into the residue sequence of the target state. If the residue sequences match, Move (ii) ensures we can arrange the integers $1, \dots, n$ into the desired final order.
-----------book page break-----------
We construct an invariant based on the positions of the zeros (numbers divisible by $3$) and the order of the non-zero residues. Let $Z$ be the set of indices $i$ such that $r_i = 0$. Let $S_{NZ}$ be the subsequence of $R$ formed by removing all zeros. We define the quantity $I$ as:
\[ I \equiv \left( \sum_{k \in Z} k \right) + \text{inv}(S_{NZ}) \pmod 2 \]
where $\text{inv}(S_{NZ})$ is the number of inversions in the subsequence of non-zero residues.
\[ I \equiv \left( \sum_{k \in Z} k \right) + \text{inv}(S_{NZ}) \pmod 2 \]
where $\text{inv}(S_{NZ})$ is the number of inversions in the subsequence of non-zero residues.
For Move (ii), $R$ does not change, so $I$ is constant.
For Move (i), if applied to a permutation of $\{0, 1, 2\}$ (e.g., $(1, 2, 0) \to (2, 0, 1)$ at indices $k, k+1, k+2$):
First, the zero moves from index $k+2$ to $k+1$. The sum of indices changes by $-1$.
Second, the pair $(1, 2)$ in $S_{NZ}$ becomes $(2, 1)$. The number of inversions changes by $\pm 1$.
The total change in $I$ is $\Delta I \equiv -1 + (\pm 1) \equiv 0 \pmod 2$.
Thus, the parity $I$ is invariant under all allowed moves.
For Move (i), if applied to a permutation of $\{0, 1, 2\}$ (e.g., $(1, 2, 0) \to (2, 0, 1)$ at indices $k, k+1, k+2$):
First, the zero moves from index $k+2$ to $k+1$. The sum of indices changes by $-1$.
Second, the pair $(1, 2)$ in $S_{NZ}$ becomes $(2, 1)$. The number of inversions changes by $\pm 1$.
The total change in $I$ is $\Delta I \equiv -1 + (\pm 1) \equiv 0 \pmod 2$.
Thus, the parity $I$ is invariant under all allowed moves.
We compare the invariant $I_{\text{start}}$ of the initial sequence with $I_{\text{end}}$ of the target sequence.
Initial Sequence: $(1, 2, 0, 1, 2, 0, \dots)$.
Target Sequence: $(n, 1, 2, \dots, n-1)$ (Cyclic right shift by $1$).
Initial Sequence: $(1, 2, 0, 1, 2, 0, \dots)$.
Target Sequence: $(n, 1, 2, \dots, n-1)$ (Cyclic right shift by $1$).
-----------book page break-----------
$\text{Case 1}$: $n \equiv 2 \pmod 3$
Let $n = 3k + 2$. The number of zeros is $k$.
Shift of Zeros: In the target sequence, every element is shifted to the right by $1$ position. Thus, the sum of zero positions increases by exactly $k$.
Shift of Non-Zeros: The subsequence $S_{NZ}$ has length $2k+2$. The target non-zero sequence is obtained by swapping every $(1, 2)$ pair into $(2, 1)$. There are $k+1$ such pairs.
Total Change: $\Delta I = k + (k+1) = 2k + 1 \equiv 1 \pmod 2$.
Since $\Delta I \neq 0$, the transformation is impossible.
Let $n = 3k + 2$. The number of zeros is $k$.
Shift of Zeros: In the target sequence, every element is shifted to the right by $1$ position. Thus, the sum of zero positions increases by exactly $k$.
Shift of Non-Zeros: The subsequence $S_{NZ}$ has length $2k+2$. The target non-zero sequence is obtained by swapping every $(1, 2)$ pair into $(2, 1)$. There are $k+1$ such pairs.
Total Change: $\Delta I = k + (k+1) = 2k + 1 \equiv 1 \pmod 2$.
Since $\Delta I \neq 0$, the transformation is impossible.
$\text{Case 2}$: $n \equiv 0 \text{ or } 1 \pmod 3$
In these cases, $\Delta I \equiv 0 \pmod 2$. Since Move (i) generates the alternating group on residues and Move (ii) allows reordering within classes, the transformation is possible.
In these cases, $\Delta I \equiv 0 \pmod 2$. Since Move (i) generates the alternating group on residues and Move (ii) allows reordering within classes, the transformation is possible.
$\therefore$ The transformation is possible if and only if $n \not\equiv 2 \pmod 3$. The set of valid $n$ is:
\[ n \in \{3, 4, 6, 7, 9, 10, \dots\} \]
$\therefore 68 \equiv 287 \equiv 2\ (mod\ 3) \not\in S$ and
\[ n \in \{3, 4, 6, 7, 9, 10, \dots\} \]
$\therefore 68 \equiv 287 \equiv 2\ (mod\ 3) \not\in S$ and
$355 \equiv 1\ (mod\ 3) \in S$, also,
$72 \equiv 0\ (mod\ 3) \in S$