International Mathematics Competition
for University Students
2026

IMC2026: Day 1, Problem 3

Problem 3. Consider a deck of \(\displaystyle n\geq 2\) cards labeled \(\displaystyle 1,2,\ldots,n\). An alternating shuffle of the deck is performed as follows. We split the deck into two non-empty stacks. We then sort the first stack in increasing order, and the second stack in decreasing order. Finally, we alternately take cards from the first and second stacks (starting with the first). If one of the stacks runs out, the remaining cards from the other stack are placed at the end. How many different final orders of the deck can be obtained in this way?
[0.5cm] Example: Suppose \(\displaystyle n=6\), the first stack is \(\displaystyle A=(1,\,3)\), and the second stack is \(\displaystyle B=(6,\,5,\,4,\,2)\). Then the order resulting from the alternating shuffle is \(\displaystyle (1,\,6,\,3,\,5,\,4,\,2)\).

Daniel Volostnov, Neapolis University Paphos, Cyprus

Solution. Setup. Define the reference string \(\displaystyle \mathcal{S} = ABAB\cdots\) of length \(\displaystyle n\). For a given subset \(\displaystyle Y\) of cards in the first stack, let \(\displaystyle \mathcal{S}_P \in \{A,B\}^n\) be the source string of \(\displaystyle P(Y)\): \(\displaystyle (\mathcal{S}_P)_i = A\) if the card at position \(\displaystyle i\) of \(\displaystyle P\) came from deck \(\displaystyle A\), and \(\displaystyle (\mathcal{S}_P)_i = B\) otherwise.

For \(\displaystyle i \in \{1,2,\ldots,n\}\), define

\(\displaystyle B_i = \bigl\{\,P(Y) \;\big|\; \text{the smallest index } j \text{ with } (\mathcal{S}_P)_j \neq \mathcal{S}_j \text{ equals } i \bigr\}, \)

and let \(\displaystyle B_{n+1} = \bigl\{\,P(Y) \;\big|\; \mathcal{S}_P = \mathcal{S}\bigr\}\) (i.e. the source string matches the reference string perfectly).

For each \(\displaystyle i\), let \(\displaystyle G_i\) be the directed graph on vertex set \(\displaystyle \{1,2,\ldots,n\}\) where there is an edge from \(\displaystyle x\) to \(\displaystyle y\) whenever \(\displaystyle P_x > P_y\), encoding the relative-order structure common to all orders of \(\displaystyle B_i\).

Throughout, assume \(\displaystyle i < j\).

Step 1. \(\displaystyle B_i \cap B_j = \varnothing\) whenever \(\displaystyle j - i\) is odd.

Consider the graphs \(\displaystyle G_i\) and \(\displaystyle G_j\), and look at vertices \(\displaystyle n-1\) and \(\displaystyle n\). For \(\displaystyle i\) and \(\displaystyle j\) of different parity, the edge between \(\displaystyle n-1\) and \(\displaystyle n\) is directed in opposite ways in \(\displaystyle G_i\) and \(\displaystyle G_j\). If a common order existed in \(\displaystyle B_i \cap B_j\), it would simultaneously require \(\displaystyle P_{n-1} > P_n\) and \(\displaystyle P_{n-1} < P_n\), a contradiction.

Step 2. \(\displaystyle B_i \cap B_j = \varnothing\) whenever \(\displaystyle j - i\) is even and \(\displaystyle j - i > 2\).

Consider the graphs \(\displaystyle G_i\) and \(\displaystyle G_j\) at vertices \(\displaystyle i\) and \(\displaystyle i+2\). By the same argument as in Step 1, the edges between these vertices point in opposite directions, giving a contradiction.

Step 3. \(\displaystyle B_{n+1}\) creates a single exceptional overlap with \(\displaystyle B_n\).

The set \(\displaystyle B_{n+1}\) is on equal footing with the other \(\displaystyle B_i\): Steps 1 and 2 apply to it as well, so \(\displaystyle B_{n+1}\) is disjoint from all \(\displaystyle B_i\) except possibly \(\displaystyle B_{n-1}\) and \(\displaystyle B_n\) (by parity). In fact, \(\displaystyle B_{n+1}\) and \(\displaystyle B_n\) share exactly one order: the sequence \(\displaystyle P = (1, n, 2, n{-}1, \ldots)\) produced by \(\displaystyle A = \{1, 2, \ldots, \lceil n/2 \rceil\}\) and \(\displaystyle B = \{n, n{-}1, \ldots, \lfloor n/2 \rfloor + 1\}\). This is because the edge \(\displaystyle n{-}1 \to n\) does not appear in \(\displaystyle G_{n+1}\), so the graph constraint of \(\displaystyle G_n\) is also satisfied. No other order of \(\displaystyle B_{n+1}\) lies in \(\displaystyle B_n\).

From Steps 1–3 it follows that \(\displaystyle B_1 \cup B_2 \cup \cdots \cup B_{n+1} = \{P(Y) : Y \subseteq S\}\), and the only non-empty pairwise intersections are \(\displaystyle D_i := B_i \cap B_{i+2}\) for \(\displaystyle i = 1, \ldots, n-1\), together with the single exceptional order \(\displaystyle |B_n \cap B_{n+1}| = 1\).

Step 4. Computing \(\displaystyle |B_i|\).

The graph \(\displaystyle G_i\) consists of two directed paths (``bamboo sticks''). Since each \(\displaystyle B_i\) encodes all possible subsets \(\displaystyle Y\) whose source string first deviates from \(\displaystyle \mathcal{S}\) at position \(\displaystyle i\), the bamboo lengths depend on the parity of \(\displaystyle i\):

• if \(\displaystyle i\) is odd: \(\displaystyle |B_i| = \displaystyle\binom{n}{(i-1)/2}\),
• if \(\displaystyle i\) is even: \(\displaystyle |B_i| = \displaystyle\binom{n}{n - i/2 + 1}\).

Since all \(\displaystyle B_i\) together (for \(\displaystyle i = 1, \ldots, n+1\)) partition the set of source-string encodings of all \(\displaystyle 2^n\) subsets, we have

\(\displaystyle \sum_{i=1}^{n+1} |B_i| = 2^n. \)

Step 5. Computing the overlaps \(\displaystyle |D_i|\) where \(\displaystyle D_i = B_i \cap B_{i+2}\).

From Steps 1 and 2, \(\displaystyle D_i \cap D_j = \varnothing\) for \(\displaystyle i \neq j\). Consider the union graph \(\displaystyle G'\) of \(\displaystyle G_i\) and \(\displaystyle G_{i+2}\). For odd \(\displaystyle i\), the graph \(\displaystyle G'\) is almost identical to \(\displaystyle G_{i+2}\) except that edges \(\displaystyle i \to i+1\) and \(\displaystyle i+1 \to i+2\) are added, which fix the relative order of \(\displaystyle (i+1)/2\) vertices. Removing these determined vertices leaves two bamboo sticks, one with \(\displaystyle (i-1)/2\) vertices. Hence for odd \(\displaystyle i\),

\(\displaystyle |D_i| = \binom{n - (i+1)/2}{(i-1)/2}. \)

Substituting \(\displaystyle i = 2h + 1\) gives \(\displaystyle |D_i| = \binom{n - 1 - h}{h}\).

An analogous argument for even \(\displaystyle i = 2h + 2\) yields \(\displaystyle |D_i| = \binom{n - 2 - h}{h}\).

Step 6. Assembling the answer.

By inclusion–exclusion,

\(\displaystyle N(n) = \sum_{i=1}^{n+1} |B_i| - 1 - \sum_{i=1}^{n-1} |D_i|, \)

where \(\displaystyle -1\) accounts for the single exceptional overlap \(\displaystyle |B_n \cap B_{n+1}| = 1\) from Step 3.

The sum of \(\displaystyle |B_i|\) equals \(\displaystyle 2^n\) (Step 4).

The sum over odd-indexed \(\displaystyle D_i\) (\(\displaystyle i = 1, 3, 5, \ldots\)): when \(\displaystyle n\) is odd this equals \(\displaystyle F_n - 1\); when \(\displaystyle n\) is even this equals \(\displaystyle F_n\). Similarly, the sum over even-indexed \(\displaystyle D_i\) (\(\displaystyle i = 2, 4, 6, \ldots\)): when \(\displaystyle n\) is odd this equals \(\displaystyle F_{n-1}\); when \(\displaystyle n\) is even this equals \(\displaystyle F_{n-1} - 1\).

In both cases the total is

\(\displaystyle \sum_{i=1}^{n-1} |D_i| = F_n + F_{n-1} - 1 = F_{n+1} - 1. \)

Therefore,

\(\displaystyle \boxed{N(n) = 2^n - 1 - (F_{n+1} - 1) = 2^n - F_{n+1}}, \)

where \(\displaystyle F_{n+1} = F_n + F_{n-1}\) is the \(\displaystyle (n{+}1)\)-th Fibonacci number (with \(\displaystyle F_1 = F_2 = 1\)).