IMC 2026 · Day 1 · P3

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

For $i \in \{ 1, 2, \ldots, n \}$, define $$B_{i} = \left\{ P(Y) \mid \text{the smallest index } j \text{ with } \left( \mathcal{S}_{P} \right)_{j} \neq \mathcal{S}_{j} \text{ equals } i \right\},$$ and let $B_{n+1} = \left\{ P(Y) \mid \mathcal{S}_{P} = \mathcal{S} \right\}$ (i.e. the source string matches the reference string perfectly).

For each $i$, let $G_{i}$ be the directed graph on vertex set $\{ 1, 2, \ldots, n \}$ where there is an edge from $x$ to $y$ whenever $P_{x} > P_{y}$, encoding the relative-order structure common to all orders of $B_{i}$.

Throughout, assume $i < j$.

Step 1. $B_{i} \cap B_{j} = \varnothing$ whenever $j - i$ is odd. Consider the graphs $G_{i}$ and $G_{j}$, and look at vertices $n-1$ and $n$. For $i$ and $j$ of different parity, the edge between $n-1$ and $n$ is directed in opposite ways in $G_{i}$ and $G_{j}$. If a common order existed in $B_{i} \cap B_{j}$, it would simultaneously require $P_{n-1} > P_{n}$ and $P_{n-1} < P_{n}$, a contradiction.

Step 2. $B_{i} \cap B_{j} = \varnothing$ whenever $j - i$ is even and $j - i > 2$. Consider the graphs $G_{i}$ and $G_{j}$ at vertices $i$ and $i+2$. By the same argument as in Step 1, the edges between these vertices point in opposite directions, giving a contradiction.

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

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

Step 4. Computing $\left| B_{i} \right|$. The graph $G_{i}$ consists of two directed paths (“bamboo sticks”). Since each $B_{i}$ encodes all possible subsets $Y$ whose source string first deviates from $\mathcal{S}$ at position $i$, the bamboo lengths depend on the parity of $i$:

• if $i$ is odd: $\left| B_{i} \right| = \binom{n}{(i-1) / 2}$,
• if $i$ is even: $\left| B_{i} \right| = \binom{n}{n - i / 2 + 1}$.

Since all $B_{i}$ together (for $i = 1, \ldots, n+1$) partition the set of source-string encodings of all $2^{n}$ subsets, we have $$\sum_{i=1}^{n+1} \left| B_{i} \right| = 2^{n}.$$

Step 5. Computing the overlaps $\left| D_{i} \right|$ where $D_{i} = B_{i} \cap B_{i+2}$. From Steps 1 and 2, $D_{i} \cap D_{j} = \varnothing$ for $i \neq j$. Consider the union graph $G^{\prime}$ of $G_{i}$ and $G_{i+2}$. For odd $i$, the graph $G^{\prime}$ is almost identical to $G_{i+2}$ except that edges $i \rightarrow i+1$ and $i+1 \rightarrow i+2$ are added, which fix the relative order of $(i+1) / 2$ vertices. Removing these determined vertices leaves two bamboo sticks, one with $(i-1) / 2$ vertices. Hence for odd $i$, $$\left| D_{i} \right| = \binom{n - (i+1) / 2}{(i-1) / 2}.$$ Substituting $i = 2 h + 1$ gives $\left| D_{i} \right| = \binom{n - 1 - h}{h}$.

An analogous argument for even $i = 2 h + 2$ yields $\left| D_{i} \right| = \binom{n - 2 - h}{h}$.

Step 6. Assembling the answer. By inclusion–exclusion, $$N(n) = \sum_{i=1}^{n+1} \left| B_{i} \right| - 1 - \sum_{i=1}^{n-1} \left| D_{i} \right|,$$ where $-1$ accounts for the single exceptional overlap $\left| B_{n} \cap B_{n+1} \right| = 1$ from Step 3.

The sum of $\left| B_{i} \right|$ equals $2^{n}$ (Step 4).

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

In both cases the total is $$\sum_{i=1}^{n-1} \left| D_{i} \right| = F_{n} + F_{n-1} - 1 = F_{n+1} - 1.$$

Therefore, $$\boxed{N(n) = 2^{n} - 1 - \left( F_{n+1} - 1 \right) = 2^{n} - F_{n+1}},$$ where $F_{n+1} = F_{n} + F_{n-1}$ is the $(n+1)$-th Fibonacci number (with $F_{1} = F_{2} = 1$).