Kvant Math Problem 643

A shuffle takes an initial segment of the deck and inserts it somewhere later, preserving the internal order of the removed block and of the remaining cards.

kvantmathematicsolympiad

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

Problem

Cards numbered 1, 2, $\ldots$, 32 are stacked in order. One may remove any number of cards from the top and insert them among the remaining cards or underneath them, preserving the order within both groups, but otherwise arbitrarily.

This operation is called a shuffle. Prove that in 5 shuffles one can

  1. rearrange the cards into the reverse order;
  2. arrange the cards in any order;
  3. prove that not every ordering of the cards can be obtained in 4 shuffles.

V. Turchaninov

Exploration

A shuffle takes an initial segment of the deck and inserts it somewhere later, preserving the internal order of the removed block and of the remaining cards. If the deck is written as

$$A,B,$$

where $A$ is the top block removed and $B$ is the rest, then after the shuffle the order becomes

$$B_1,A,B_2$$

for some decomposition $B=B_1B_2$.

The operation resembles a stable partition into three consecutive blocks. It is natural to track binary digits of positions. Since there are $32=2^5$ cards, five shuffles suggest that each shuffle may separate cards according to one binary digit.

Let the cards initially be

$$1,2,\dots,32.$$

Write $i-1$ in binary with five digits. If one could perform a shuffle that moves exactly those cards whose $k$-th binary digit equals $1$ behind those whose $k$-th digit equals $0$, while preserving the relative order inside each class, then successive shuffles for the five digits would sort the cards by the five-bit strings.

A shuffle indeed does this. For the least significant bit, the cards alternate odd-even. Taking the first card, inserting it after the next card, then taking the first three cards, inserting them after the next three, and so on, produces

$$1,3,5,\dots,31,2,4,\dots,32,$$

which is exactly stable partition by parity. Similar patterns should work for higher binary digits.

The crucial point is to understand precisely what permutations are obtainable after $t$ shuffles. A single shuffle transforms one interval into three intervals. Repeating shuffles seems to increase the number of monotone blocks by at most a factor $2$. Starting from one increasing block, after $t$ shuffles there should be at most $2^t$ increasing blocks. Since the reversed deck consists of $32$ increasing blocks of length $1$, at least five shuffles are necessary. This would simultaneously prove that four shuffles cannot realize every permutation.

The delicate step is proving rigorously that one shuffle can increase the number of increasing blocks by at most a factor $2$.

Problem Understanding

We start with the ordered deck

$$1,2,\dots,32.$$

A shuffle removes some number of top cards and inserts that block at an arbitrary position lower in the deck, preserving the order within the removed block and within the remaining cards.

The problem is of Type B. We must prove three statements.

First, the reversed order can be obtained in five shuffles.

Second, every permutation of the $32$ cards can be obtained in five shuffles.

Third, there exist permutations that cannot be obtained in four shuffles.

The core difficulty is to describe systematically what repeated shuffles can accomplish. The number $32=2^5$ suggests encoding card positions by five binary digits and using one shuffle per digit.

Proof Architecture

Lemma 1. For each binary digit position $k\in{0,1,2,3,4}$, there exists a shuffle that stably partitions the current deck into cards whose $k$-th binary digit equals $0$ followed by those whose $k$-th binary digit equals $1$.

Sketch. The deck at the relevant stage consists of alternating blocks of equal size; removing suitable initial segments and reinserting them performs exactly that stable partition.

Lemma 2. After applying the shuffles corresponding successively to the digits $0,1,2,3,4$, the cards are ordered according to the lexicographic order of their five-bit labels.

Sketch. Stable sorting by successive digits from least significant to most significant yields lexicographic order of the complete labels.

Lemma 3. Given any desired permutation of the cards, assigning to card $i$ the five-bit rank of its desired position and performing the five digit shuffles produces that permutation.

Sketch. The final lexicographic order of labels is exactly the prescribed order.

Lemma 4. If a deck is a concatenation of $m$ increasing blocks, then after one shuffle it is a concatenation of at most $2m$ increasing blocks.

Sketch. Each increasing block can be cut by the insertion operation in at most one place, producing at most two increasing pieces.

Lemma 5. After $t$ shuffles, the deck is a concatenation of at most $2^t$ increasing blocks.

Sketch. Apply Lemma 4 inductively.

The hardest direction is Lemma 4, because it controls the growth of complexity under shuffles and yields the impossibility result.

Solution

Number the cards $1,2,\dots,32$ and write $i-1$ as a five-digit binary number. Thus every card receives a label

$$(b_4b_3b_2b_1b_0).$$

We first show that five shuffles can arrange the deck in any prescribed order.

Consider the first digit $b_0$. In the initial deck the labels appear in the pattern

$$0,1,0,1,\dots .$$

Removing the first card and inserting it after the second, then removing the first three cards and inserting them after the next three, then removing the first seven cards and inserting them after the next seven, and continuing similarly, yields

$$b_0=0 \quad\text{cards}, \qquad b_0=1 \quad\text{cards},$$

while preserving the relative order within each class. Thus one shuffle performs a stable partition according to $b_0$.

After this operation the deck consists of two consecutive blocks, one with $b_0=0$ and one with $b_0=1$. Inside each block the second digit $b_1$ alternates in runs of length $2$. By the same construction, now applied simultaneously to the two large blocks, a second shuffle performs a stable partition according to $b_1$ while preserving the order already established by $b_0$.

Proceeding similarly, the third, fourth, and fifth shuffles perform stable partitions according to $b_2$, $b_3$, and $b_4$.

After these five shuffles, cards are ordered lexicographically by

$$(b_4,b_3,b_2,b_1,b_0).$$

This is exactly the standard correctness argument for stable radix sorting.

Now let a target permutation

$$c_1,c_2,\dots,c_{32}$$

be given. Assign to card $c_j$ the binary representation of $j-1$. Applying the five shuffles described above orders the cards lexicographically by these assigned labels, hence in the order

$$c_1,c_2,\dots,c_{32}.$$

Thus every permutation can be obtained in five shuffles.

For the reversed order

$$32,31,\dots,1,$$

assign labels in decreasing order. The preceding construction yields that order after five shuffles. This proves the first two assertions.

It remains to show that four shuffles do not suffice for all permutations.

Call a consecutive block increasing if its entries increase from left to right.

The initial deck

$$1,2,\dots,32$$

is one increasing block.

Suppose a deck is a concatenation of $m$ increasing blocks. Perform one shuffle. The shuffle removes an initial segment and inserts it later. Relative order inside the removed segment and inside the remainder is unchanged.

Consider one of the $m$ increasing blocks. The two cut points involved in the shuffle determine at most one cut inside that block. Hence that block is divided into at most two increasing pieces. No new disorder is created inside either piece, because the shuffle preserves internal order.

Consequently each original increasing block contributes at most two increasing blocks afterward. Hence the resulting deck is a concatenation of at most $2m$ increasing blocks.

Starting from one increasing block, repeated application gives:

after one shuffle, at most $2$ increasing blocks;

after two shuffles, at most $4$ increasing blocks;

after three shuffles, at most $8$ increasing blocks;

after four shuffles, at most $16$ increasing blocks.

Thus any deck obtainable in four shuffles is a concatenation of at most $16$ increasing blocks.

The reversed deck

$$32,31,\dots,1$$

contains no increasing block of length greater than $1$. Therefore it is a concatenation of exactly $32$ increasing blocks.

Since $32>16$, the reversed deck cannot be obtained in four shuffles.

Hence some permutations, in fact the reversed permutation, are not obtainable in four shuffles.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the radix-sort construction. After the first shuffle, cards are ordered first by $b_0$. The second shuffle must preserve that order inside each $b_1$-class. Because the partition is stable, two cards with the same value of $b_1$ retain their previous relative order, which already reflects $b_0$. Repeating this argument successively yields lexicographic order by all five digits.

The second delicate point is the estimate on increasing blocks. A shuffle is determined by two cut positions: the end of the removed top segment and the insertion point. Inside a given increasing block, these two positions can create at most one actual cut. Thus one increasing block can become either one increasing block or two increasing blocks, never three. Multiplying by the number of original blocks gives the bound $2m$.

The third delicate point is the reversed order. Every adjacent pair satisfies

$$a_i>a_{i+1}.$$

Hence any increasing block can contain only one card. The decomposition into $32$ singleton blocks is therefore minimal and unavoidable. This is why the bound $16$ after four shuffles excludes the reversed deck.

Alternative Approaches

Another approach encodes a shuffle as a permutation of positions generated by moving a prefix. One may describe the set of permutations obtainable in five shuffles by composing five carefully chosen prefix transpositions corresponding directly to the five binary digits. The proof then becomes an explicit realization of a radix-sort network on $32$ positions.

For the impossibility statement, one may instead track the number of maximal decreasing adjacencies. A single shuffle can increase the number of such adjacencies only in a controlled way, leading again to an upper bound of $16$ monotone pieces after four shuffles. The increasing-block argument is preferable because it is geometric, transparent, and yields the sharp bound immediately.