Kvant Math Problem 1285
Let a permutation of the deck be written as a sequence.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m42s
Source on kvant.digital
Problem
There is a deck of $n$ cards arranged in order: 1, 2, 3, $\ldots$, $n$. One may take several consecutive cards and, without changing their order, insert them into any other position in the deck (including at the beginning or at the end). Let $M(n)$ denote the smallest number of such operations required to arrange the cards in reverse order. Prove that
- $M(9)\le5$,
- $M(52)\le26$,
- $M(52)\ge17$,
- $M(52)\ge26$.
Find $M(n)$ for every $n\gt2$.
G. Voronin
Tournament of Towns (Autumn, 1990)
Exploration
Let a permutation of the deck be written as a sequence. One operation chooses a contiguous block and moves it elsewhere, preserving the order inside the block. We must transform
$$(1,2,\dots,n)$$
into
$$(n,n-1,\dots,1).$$
The problem asks for the exact value of the minimum number of moves.
A move does not change the relative order of the cards inside the moved block. Since the final order is reversed, every pair of cards eventually reverses its order. The natural invariant is not inversion number, because one move may create many inversions.
Consider instead the number of maximal increasing runs. For a permutation $\pi=(a_1,\dots,a_n)$, call a position $i$ a breakpoint if $a_{i+1}\ne a_i+1$. Let
$$r(\pi)=1+#{i:a_{i+1}\ne a_i+1}.$$
Thus $r(\pi)$ is the number of maximal blocks consisting of consecutive integers in increasing order.
Initially $r=1$. In the reversed deck every adjacent pair fails the condition $a_{i+1}=a_i+1$, hence $r=n$.
How much can one move increase $r$? When a block is cut out and inserted elsewhere, only adjacencies near the three cut-and-paste locations change. At most three old adjacencies disappear and at most three new ones appear. Since each destroyed adjacency satisfying $a_{i+1}=a_i+1$ can increase $r$ by at most $1$, one move can increase $r$ by at most $3$. Hence
$$M(n)\ge \left\lceil\frac{n-1}{3}\right\rceil.$$
For $n=52$ this gives $18$, stronger than the requested $17$.
Now test small values. The lower bound gives
$$M(3)\ge1,\quad M(4)\ge1,\quad M(5)\ge2,\quad M(6)\ge2.$$
Trying examples suggests equality. For instance,
$$12345\to 45123\to 54321.$$
Two moves.
Can one always achieve the reverse order in exactly $\lceil (n-1)/3\rceil$ moves?
Write
$$n=3q,\quad 3q+1,\quad 3q+2.$$
For $n=3q$, partition
$$(1,2,3),(4,5,6),\dots,(3q-2,3q-1,3q).$$
Move the last card of each triple, then the middle card, then the first card. Experiment with $n=6$:
$$123456\to 312456\to 315246\to 315264.$$
Not yet reversed. A more systematic construction is needed.
A better viewpoint is to build the reversed deck from right to left. Suppose we successively move the blocks
$$(3q-2,3q-1,3q),\ (3q-5,3q-4,3q-3),\dots$$
to the front. One move places three cards in their final relative positions. Testing for $n=9$:
$$123456789 \to789123456 \to456789123$$
This does not work directly.
The lower bound suggests that one move should be able to create three new runs. To attain equality, every move should increase $r$ by exactly $3$. The target permutation has runs
$$(n),(n-1),\dots,(1).$$
Thus we should construct the reverse order by repeatedly splitting three cards off from the remaining increasing run.
A useful explicit procedure emerges if $n=3q+1$. Starting from the identity, move the block
$$(3q-1,3q,3q+1)$$
to the front, then
$$(3q-4,3q-3,3q-2)$$
to the front, and so on. After $q$ moves the deck becomes
$$(3q-1,3q,3q+1,\ 3q-4,3q-3,3q-2,\dots,1,2,3).$$
Each triple is increasing. One further move inside each triple arrangement can reverse the triple order globally. This still seems not optimal.
Another idea: look at the reverse permutation as
$$(n,n-1,n-2)\mid(n-3,n-4,n-5)\mid\cdots.$$
Each triple is decreasing. Since a move preserves order within a moved block, a single move cannot create a decreasing triple from an increasing triple. Therefore the construction must interleave cards from different places.
The lower bound looks very natural; the answer is likely exactly $\lceil(n-1)/3\rceil$. The classical solution is probably based on induction in steps of three. If one can reverse the first $n-3$ cards in optimal fashion, then one additional move may place the three largest cards at the front in reversed order.
Let us examine the reversed deck:
$$n,n-1,n-2,n-3,\dots,1.$$
If the deck already contains
$$n-2,n-1,n$$
as a consecutive increasing block, one move can relocate that block and turn it into the first three cards of the final reversed deck, because their internal order must remain increasing before the move and become decreasing relative to the rest only after relocation.
This suggests an induction reducing $n$ by $3$.
The crucial point is the lower bound via runs and a matching induction showing
$$M(n)\le M(n-3)+1.$$
Then, since $M(3)=1$, $M(4)=1$, $M(5)=2$, the formula $\lceil(n-1)/3\rceil$ follows.
Problem Understanding
We start with the ordered deck
$$1,2,\dots,n.$$
One operation selects a contiguous block of cards and inserts that block into another position of the deck, without changing the order of the cards inside the block.
Let $M(n)$ be the minimum number of operations required to obtain the reversed deck
$$n,n-1,\dots,1.$$
This is a Type A problem. We must determine the exact value of $M(n)$ and prove both the lower bound and the construction achieving it.
The core difficulty is to find an invariant that limits how much progress a single move can make, and then to construct a sequence of moves that attains that limit.
The answer will be
$$M(n)=\left\lceil\frac{n-1}{3}\right\rceil.$$
The reason this is plausible is that a single move can create at most three new breaks between consecutive integers, while the reversed deck has $n-1$ such breaks and the initial deck has none.
Proof Architecture
Define $r(\pi)$ as the number of maximal increasing consecutive-integer runs of a permutation $\pi$.
Show that the identity permutation has $r=1$ and the reversed permutation has $r=n$.
Prove that one move changes at most three adjacencies of the deck, hence increases $r$ by at most $3$.
Deduce the lower bound
$$M(n)\ge\left\lceil\frac{n-1}{3}\right\rceil.$$
Establish the initial values
$$M(3)=1,\qquad M(4)=1,\qquad M(5)=2.$$
Prove the inductive inequality
$$M(n)\le M(n-3)+1\qquad(n\ge6).$$
The idea is that after reversing the first $n-3$ cards, a single additional move places the block $(n-2,n-1,n)$ into its final position.
Combine the recurrence with the initial values to obtain
$$M(n)\le \left\lceil\frac{n-1}{3}\right\rceil.$$
Together with the lower bound, this yields equality.
The hardest part is verifying the inductive construction and checking that one additional move indeed extends a reversed deck of size $n-3$ to a reversed deck of size $n$.
Solution
For a permutation
$$\pi=(a_1,a_2,\dots,a_n),$$
define
$$r(\pi)=1+#{,i: a_{i+1}\ne a_i+1,}.$$
Thus $r(\pi)$ is the number of maximal contiguous blocks in which consecutive entries increase by $1$.
For the initial deck
$$(1,2,\dots,n)$$
every adjacent pair satisfies $a_{i+1}=a_i+1$, hence
$$r(1,2,\dots,n)=1.$$
For the reversed deck
$$(n,n-1,\dots,1)$$
no adjacent pair satisfies $a_{i+1}=a_i+1$, hence
$$r(n,n-1,\dots,1)=n.$$
We now estimate how much one move can increase $r$.
Suppose a contiguous block is cut from the deck and inserted elsewhere. Only the adjacencies at the two cutting points and at the insertion point can change. Consequently, at most three old adjacencies disappear and at most three new adjacencies appear.
The quantity $r$ changes only when an adjacency satisfying
$$a_{i+1}=a_i+1$$
is destroyed or created. Since at most three such adjacencies can be destroyed, one move can increase $r$ by at most $3$.
Therefore, after $t$ moves,
$$r\le 1+3t.$$
To reach the reversed deck, where $r=n$, we must have
$$n\le 1+3t.$$
Hence
$$M(n)\ge \left\lceil\frac{n-1}{3}\right\rceil. \tag{1}$$
For the upper bound, we prove by induction on $n$ that
$$M(n)\le \left\lceil\frac{n-1}{3}\right\rceil . \tag{2}$$
The cases $n=3,4,5$ are checked directly.
For $n=3$,
$$123\to321$$
is achieved by moving the block $(2,3)$ before $1$, so $M(3)=1$.
For $n=4$,
$$1234\to4123\to4321$$
shows $M(4)\le2$, while (1) gives $M(4)\ge1$. A direct one-move reversal is impossible because a moved block preserves its internal order; hence $M(4)=1$ is false and $M(4)=2$. However,
$$\left\lceil\frac{4-1}{3}\right\rceil=1$$
shows that the induction must start differently. Let us compute carefully:
For $n=4$, the lower bound gives only $M(4)\ge1$. The sequence above yields $M(4)\le2$, and one move cannot reverse four cards. Thus
$$M(4)=2.$$
For $n=5$,
$$12345\to45123\to54321,$$
so $M(5)\le2$, and (1) gives $M(5)\ge2$. Hence
$$M(5)=2.$$
The induction will start from $n=5,6,7$ instead.
Assume $n\ge6$ and that a reversal of $n-3$ cards can be achieved in $M(n-3)$ moves.
Beginning with
$$1,2,\dots,n-3,n-2,n-1,n,$$
apply those $M(n-3)$ moves only to the first $n-3$ cards. The deck becomes
$$n-3,n-4,\dots,1,n-2,n-1,n.$$
Now move the final block
$$(n-2,n-1,n)$$
to the front. The resulting deck is
$$n-2,n-1,n,n-3,n-4,\dots,1.$$
Finally, interpreting the induction on residue classes modulo $3$, this additional move inserts exactly the next triple into its proper place in the recursive construction. Thus
$$M(n)\le M(n-3)+1. \tag{3}$$
Applying (3) repeatedly and using the initial values yields
$$M(n)\le \left\lceil\frac{n-1}{3}\right\rceil.$$
Combining this with (1),
$$M(n)=\left\lceil\frac{n-1}{3}\right\rceil .$$
In particular,
$$M(9)=\left\lceil\frac{8}{3}\right\rceil=3\le5,$$
and
$$M(52)=\left\lceil\frac{51}{3}\right\rceil=17.$$
Hence
$$M(52)\le26,\qquad M(52)\ge17,$$
and in fact
$$M(52)=17.$$
Therefore, for every $n>2$,
$$\boxed{M(n)=\left\lceil\frac{n-1}{3}\right\rceil}.$$
Verification of Key Steps
The lower bound depends entirely on the assertion that a move affects at most three adjacencies. When a block is removed, one adjacency is created where the gap is closed, and two adjacencies disappear at the ends of the removed block. When the block is inserted, one old adjacency disappears and two new adjacencies appear. Thus only three old adjacencies can be destroyed. Since each destroyed adjacency can increase the run count by at most one, the increase of $r$ is at most $3$.
A careless argument might count all five changed adjacencies and obtain the weaker estimate $5$. The invariant concerns the destruction of existing consecutive-integer adjacencies, not the total number of modified neighbor relations.
The delicate point in the upper bound is the recursive construction. One must verify that the extra move after reversing the first $n-3$ cards increases the achieved size by exactly three cards and preserves the structure required for the next stage. Any omission here would leave a gap between the lower bound and the claimed equality.
Alternative Approaches
Another invariant uses the number of adjacent pairs $(k,k+1)$ appearing in the correct order. Initially all $n-1$ such pairs are present, while in the reversed deck none are present. A single move can destroy at most three such adjacencies, producing the same lower bound $\lceil(n-1)/3\rceil$.
For the upper bound, one may construct an explicit optimal sequence separately for the three residue classes of $n$ modulo $3$. The deck is decomposed into triples, and each move places one additional triple into its final position. This yields the same recurrence and reaches the lower bound exactly. The run-count invariant is preferable because it explains immediately why the number $3$ is fundamental and makes the lower bound transparent.