Kvant Math Problem 1074
Let $m=2n+1$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 11m28s
Source on kvant.digital
Problem
A stack of $2n+1$ cards is given, from which the following two operations are allowed:
- A portion of cards is removed from the top and placed at the bottom, preserving their order;
- The top $n$ cards are placed, in order, into $n$ spaces between the bottom $n+1$ cards.
Prove that using these operations, it is impossible to obtain more than $2n(2n+1)$ distinct arrangements of the cards from the original stack.
D. V. Fomin
Leningrad City Mathematical Olympiad (1987)
Exploration
Let $m=2n+1$. Number the positions in the stack from top to bottom by
$$0,1,\dots,m-1.$$
The first operation is a rotation. If the top $k$ cards are moved to the bottom, then a card originally in position $i$ moves to position
$$i-k \pmod m.$$
Thus operation 1 is a translation on the cyclic set $\mathbb Z_m$.
The second operation is more interesting. Write the top $n$ cards as
$$A_0,A_1,\dots,A_{n-1},$$
and the bottom $n+1$ cards as
$$B_0,B_1,\dots,B_n.$$
After the operation the stack becomes
$$B_0,A_0,B_1,A_1,\dots,B_{n-1},A_{n-1},B_n.$$
Hence
$$A_i\mapsto 2i+1, \qquad B_j\mapsto 2j.$$
If $m=2n+1$, then for every position $x$,
$$x\mapsto 2x+1 \pmod m.$$
Indeed, for $x=i<n$ this gives $2i+1$, while for $x=n+j$,
$$2x+1=2(n+j)+1\equiv 2j \pmod m.$$
So the two basic operations are affine maps on $\mathbb Z_m$:
$$x\mapsto x+c, \qquad x\mapsto 2x+1.$$
Compositions of affine maps are affine. Repeated use of the second operation multiplies the coefficient by powers of $2$. This suggests that every reachable permutation has the form
$$x\mapsto 2^t x+b.$$
The crucial point is to prove that no other coefficients can occur. Once that is established, the number of reachable permutations is at most
$$m\cdot \operatorname{ord}_m(2),$$
and
$$\operatorname{ord}_m(2)\mid \varphi(m)\le m-1.$$
Therefore the total number is at most
$$m(m-1)=2n(2n+1).$$
Problem Understanding
We start with a stack of $2n+1$ distinct cards. Two operations are allowed: a cyclic rotation of the stack, and a perfect interleaving operation in which the top $n$ cards are inserted into the $n$ gaps between the bottom $n+1$ cards.
We must prove that the total number of arrangements obtainable from the initial arrangement by any sequence of these operations does not exceed
$$2n(2n+1).$$
This is a Type B problem. The task is to prove an upper bound on the size of the set of reachable arrangements.
The core difficulty is to identify the permutation group generated by the two operations and show that every reachable permutation belongs to a comparatively small family.
Proof Architecture
The first lemma states that operation 1 acts on position numbers modulo $m=2n+1$ as a translation $x\mapsto x+c$.
The second lemma states that operation 2 acts on position numbers modulo $m$ as the affine map $x\mapsto 2x+1$.
The third lemma states that every permutation generated by the two operations is an affine map
$$x\mapsto 2^t x+b \pmod m.$$
This follows because compositions of affine maps are affine, translations have coefficient $1$, and operation 2 has coefficient $2$.
The fourth lemma states that the number of distinct affine maps of the form
$$x\mapsto 2^t x+b$$
is at most
$$m,\operatorname{ord}_m(2).$$
The coefficient depends only on the residue class of $t$ modulo the multiplicative order of $2$ modulo $m$.
The final step uses
$$\operatorname{ord}_m(2)\mid \varphi(m)$$
and
$$\varphi(m)\le m-1,$$
giving the required bound.
The lemma most likely to fail under scrutiny is the identification of operation 2 with the map $x\mapsto 2x+1$. That correspondence must be checked carefully for both halves of the deck.
Solution
Let
$$m=2n+1.$$
Label the positions in the stack by the residues
$$0,1,\dots,m-1,$$
counted from top to bottom.
Each allowed operation induces a permutation of the set $\mathbb Z_m$ of position numbers.
For operation 1, suppose the top $k$ cards are moved to the bottom. A card originally in position $x$ moves to position
$$x-k \pmod m.$$
Thus operation 1 is the translation
$$R_k(x)=x-k \pmod m.$$
Now consider operation 2. Write the top $n$ cards as
$$A_0,A_1,\dots,A_{n-1},$$
and the bottom $n+1$ cards as
$$B_0,B_1,\dots,B_n.$$
After the operation the stack becomes
$$B_0,A_0,B_1,A_1,\dots,B_{n-1},A_{n-1},B_n.$$
Hence, if $0\le i<n$, the card $A_i$ moves from position $i$ to position $2i+1$.
If $0\le j\le n$, the card $B_j$ moves from position $n+j$ to position $2j$.
For $x=i<n$,
$$2x+1=2i+1.$$
For $x=n+j$,
$$2x+1=2(n+j)+1=2n+2j+1\equiv 2j \pmod m,$$
because $m=2n+1$.
Therefore operation 2 is precisely the permutation
$$T(x)=2x+1 \pmod m.$$
We next determine the form of every permutation obtainable from these operations.
The maps $R_k$ and $T$ are affine transformations of $\mathbb Z_m$:
$$x\mapsto ax+b.$$
A composition of affine transformations is again affine. The coefficient of $R_k$ is $1$, while the coefficient of $T$ is $2$.
Starting from the identity map, whose coefficient is $1=2^0$, every time a translation is composed the coefficient remains unchanged, and every time $T$ is composed the coefficient is multiplied by $2$.
By induction on the length of a sequence of operations, every reachable permutation has the form
$$x\mapsto 2^t x+b \pmod m$$
for some integer $t\ge0$ and some $b\in\mathbb Z_m$.
Let $r=\operatorname{ord}_m(2)$, the multiplicative order of $2$ modulo $m$. Since $m$ is odd, $2$ is invertible modulo $m$, so $r$ is well defined. Two exponents $t_1,t_2$ give the same coefficient exactly when
$$2^{t_1}\equiv 2^{t_2}\pmod m,$$
that is, when $t_1\equiv t_2\pmod r$.
Consequently there are at most $r$ possible coefficients $2^t$, and for each coefficient there are at most $m$ choices of $b$.
Hence the number of reachable permutations is at most
$$mr.$$
By Euler's theorem,
$$r=\operatorname{ord}_m(2)\mid \varphi(m).$$
Since $m>1$,
$$\varphi(m)\le m-1.$$
Therefore
$$mr\le m\varphi(m)\le m(m-1).$$
Substituting $m=2n+1$ yields
$$m(m-1)=(2n+1)\cdot 2n.$$
Thus the number of arrangements obtainable from the original stack does not exceed
$$2n(2n+1).$$
This completes the proof.
∎
Verification of Key Steps
The identification of operation 2 must be checked separately on the two parts of the deck.
For a top card in position $i<n$, the new position is $2i+1$. For a bottom card in position $n+j$, the new position is $2j$. The congruence
$$2(n+j)+1\equiv 2j \pmod{2n+1}$$
shows that a single formula,
$$x\mapsto 2x+1,$$
covers both cases. Omitting the second verification would leave a gap.
The statement that every reachable permutation has coefficient $2^t$ requires closure under composition. If
$$f(x)=2^{a}x+b, \qquad g(x)=2^{c}x+d,$$
then
$$g(f(x)) = 2^{a+c}x+(2^c b+d).$$
The coefficient remains a power of $2$. Without this computation, additional coefficients might accidentally be admitted.
The counting argument depends on the multiplicative order of $2$ modulo $m$. Since $m=2n+1$ is odd,
$$\gcd(2,m)=1,$$
so $2$ is a unit modulo $m$ and the order is defined. If $m$ were even, the argument would fail at this point.
Alternative Approaches
One may describe the positions as the cyclic group $\mathbb Z_{2n+1}$ from the outset and observe that the generated group is contained in the affine group
$$\operatorname{AGL}(1,\mathbb Z_{2n+1}).$$
The first operation gives all translations, while the second contributes the dilation by $2$. The generated subgroup is therefore the semidirect product of the translation group with the cyclic subgroup generated by $2$. Its order is
$$(2n+1)\operatorname{ord}_{2n+1}(2),$$
from which the bound follows immediately.
The proof presented above avoids group-theoretic terminology and derives the same structure directly from the action on positions. This keeps every step elementary and makes the counting argument transparent.