Kvant Math Problem 210
The operation does not act on individual digits.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m21s
Source on kvant.digital
Problem
Consider sequences consisting of 3000 digits, each either 1 or 2. In such a sequence, it is allowed to swap any two adjacent triples of digits. Two sequences are called equivalent if one can be transformed into the other by a finite number of such swaps. How many inequivalent sequences exist in total?
G. A. Gurevich
Exploration
The operation does not act on individual digits. A sequence of length $3000$ naturally splits into $1000$ consecutive triples:
$$(a_1,a_2,a_3), (a_4,a_5,a_6),\dots, (a_{2998},a_{2999},a_{3000}).$$
Swapping two adjacent triples exchanges two neighboring blocks of length $3$.
The first question is whether anything inside a triple can change. It cannot. Every allowed move only changes the order of whole triples.
For a shorter example, suppose there are only three triples, denoted by symbols $A,B,C$. By successive adjacent swaps one can transform
$$ABC \to BAC \to BCA,$$
and similarly obtain any permutation. Thus the operation generates all permutations of the triples.
Hence two sequences are equivalent precisely when they contain the same collection of triples, counted with multiplicity. The order of the triples is irrelevant.
There are $2^3=8$ possible triples:
$$111,\ 112,\ 121,\ 122,\ 211,\ 212,\ 221,\ 222.$$
An equivalence class is determined by the numbers of occurrences of these eight types. If these numbers are
$$x_1,x_2,\dots,x_8,$$
then
$$x_1+x_2+\cdots+x_8=1000.$$
The problem reduces to counting the nonnegative integer solutions of this equation. The only place where an error could hide is the claim that adjacent triple swaps generate all permutations of the $1000$ triples, so that no further invariant survives. That point must be proved carefully.
Problem Understanding
We have sequences of $3000$ digits, each digit equal to $1$ or $2$. The sequence is divided into $1000$ consecutive triples. An allowed move swaps two neighboring triples. Two sequences are equivalent if one can be obtained from the other by finitely many such moves.
This is a Type A problem. We must determine all equivalence classes, or equivalently count them.
The answer should be
$$\binom{1007}{7}.$$
The reason is that the only information preserved by the moves is how many triples of each of the eight possible types occur. Every arrangement of the same multiset of triples can be reached by adjacent swaps.
Proof Architecture
The first lemma states that every allowed move preserves the number of occurrences of each of the eight triple types, because it merely exchanges two whole triples.
The second lemma states that any permutation of the $1000$ triples can be achieved by a finite sequence of adjacent triple swaps, because adjacent transpositions generate the full symmetric group.
The third lemma states that two sequences are equivalent if and only if they have the same numbers of occurrences of each triple type; one direction follows from the first lemma, the other from the second.
The final counting claim states that equivalence classes are in bijection with nonnegative integer solutions of
$$x_1+\cdots+x_8=1000,$$
whose number is given by the stars and bars formula.
The hardest direction is proving that equality of the eight multiplicities is sufficient for equivalence. Any mistake there would leave open the possibility of an additional invariant.
Solution
Divide every sequence into its $1000$ consecutive triples. Denote these triples by
$$T_1,T_2,\dots,T_{1000}.$$
Each $T_i$ is one of the eight words
$$111,\ 112,\ 121,\ 122,\ 211,\ 212,\ 221,\ 222.$$
Let the numbers of occurrences of these eight types be
$$x_1,x_2,\dots,x_8.$$
Then
$$x_1+x_2+\cdots+x_8=1000.$$
Every allowed move swaps two adjacent triples. Such a move changes only the order of the triples and does not alter any triple itself. Consequently the numbers
$$x_1,x_2,\dots,x_8$$
remain unchanged under every move. Hence equivalent sequences must have the same values of all eight multiplicities.
It remains to prove the converse.
Consider two sequences having the same multiplicities of all eight triple types. Regard each sequence simply as an ordered list of $1000$ triples.
An allowed move exchanges two neighboring entries in this list. Thus every allowed move is an adjacent transposition.
Any permutation of a finite list can be obtained as a product of adjacent transpositions. One way to see this is the following. Starting from a desired target ordering, move its first triple to the first position by repeatedly swapping it leftward with its neighbor. Then move the triple that should occupy the second position into that position, again by repeated adjacent swaps. Continuing in this manner eventually produces the target ordering. Therefore every permutation of the $1000$ triples can be realized by allowed moves.
Since the two sequences contain exactly the same multiset of triples, one ordering of that multiset can be transformed into the other by a suitable permutation of the $1000$ positions. Since every such permutation is obtainable by adjacent triple swaps, the two sequences are equivalent.
Thus two sequences are equivalent if and only if they have the same multiplicities
$$x_1,x_2,\dots,x_8.$$
Therefore equivalence classes are in one to one correspondence with the nonnegative integer solutions of
$$x_1+x_2+\cdots+x_8=1000.$$
The number of such solutions is given by the stars and bars formula:
$$\binom{1000+8-1}{8-1} = \binom{1007}{7}.$$
Hence the total number of inequivalent sequences is
$$\boxed{\binom{1007}{7}}.$$
Verification of Key Steps
The first delicate point is whether the operation can change anything inside a triple. A swap replaces
$$\cdots T_i,T_{i+1}\cdots$$
by
$$\cdots T_{i+1},T_i\cdots.$$
The triples themselves are untouched. Thus every triple occurring before the move occurs after the move with exactly the same multiplicity.
The second delicate point is whether adjacent triple swaps generate all permutations. For three triples,
$$ABC\to BAC$$
swaps the first two, and
$$ABC\to ACB$$
is obtained by swapping the last two. Since any permutation can be produced by successively moving elements into their required positions through neighboring exchanges, no additional restriction exists.
A careless argument might count only the total numbers of digits $1$ and $2$. That is insufficient. For example, the triples $111$ and $222$ contain the same total number of digits as the triples $112$ and $221$, but no allowed move can transform one multiset of triples into the other. The complete invariant is the eight-tuple of multiplicities of triple types.
Alternative Approaches
One may view the set of $1000$ triples as $1000$ balls placed in eight boxes according to their type. The operation acts only on the order of the balls, not on the box counts. The equivalence classes are therefore exactly the orbits of the action of the symmetric group on the $1000$ triple positions. Two sequences lie in the same orbit precisely when the eight box counts coincide. Counting orbits again reduces to counting solutions of
$$x_1+\cdots+x_8=1000,$$
which yields $\binom{1007}{7}$.
Another approach uses the language of multisets. Every equivalence class is a multiset of size $1000$ drawn from an $8$ element set of triple types. The number of such multisets is directly
$$\binom{1000+8-1}{8-1} = \binom{1007}{7}.$$
The main proof is preferable because it explicitly establishes both directions of the equivalence relation and identifies the invariant preserved by the allowed moves.