uniolympiads English

IMC 2026, Ημέρα 1, Θέμα 3

Consider a deck of n≥2n \ge 2 cards labeled 1,2,…,n1, 2, \dots, 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?

Example: Suppose n=6n = 6, the first stack is A=(1,3)A = (1, 3), and the second stack is B=(6,5,4,2)B = (6, 5, 4, 2). Then the order resulting from the alternating shuffle is (1,6,3,5,4,2)(1, 6, 3, 5, 4, 2).

Πρωτότυπο από το επίσημο PDFConsider a deck of n ≥ 2 cards labeled 1, 2, ..., 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? Example: Suppose n = 6, the first stack is A = (1, 3), and the second stack is B = (6, 5, 4, 2). Then the order resulting from the alternating shuffle is (1, 6, 3, 5, 4, 2).

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(proposed by Daniel Volostnov, Neapolis University Paphos, Cyprus)

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

For i∈{1,2,…,n}i \in \{1,2,\ldots,n\}, define

Bi={ P(Y)∣the smallest index j with (SP)j≠Sj equals i},B_i = \big\{\, P(Y) \bigm| \text{the smallest index } j \text{ with } (\mathcal{S}_P)_j \ne \mathcal{S}_j \text{ equals } i \big\},
and let Bn+1={ P(Y)∣SP=S}B_{n+1} = \big\{\, P(Y) \bigm| \mathcal{S}_P = \mathcal{S} \big\} (i.e. the source string matches the reference string perfectly).

For each ii, let GiG_i be the directed graph on vertex set {1,2,…,n}\{1,2,\ldots,n\} where there is an edge from xx to yy whenever Px>PyP_x > P_y, encoding the relative-order structure common to all orders of BiB_i.

Throughout, assume i<ji < j.

Step 1. Bi∩Bj=∅B_i \cap B_j = \varnothing whenever j−ij - i is odd.

Consider the graphs GiG_i and GjG_j, and look at vertices n−1n-1 and nn. For ii and jj of different parity, the edge between n−1n-1 and nn is directed in opposite ways in GiG_i and GjG_j. If a common order existed in Bi∩BjB_i \cap B_j, it would simultaneously require Pn−1>PnP_{n-1} > P_n and Pn−1<PnP_{n-1} < P_n, a contradiction.

Step 2. Bi∩Bj=∅B_i \cap B_j = \varnothing whenever j−ij - i is even and j−i>2j - i > 2.

Consider the graphs GiG_i and GjG_j at vertices ii and i+2i+2. By the same argument as in Step 1, the edges between these vertices point in opposite directions, giving a contradiction.

Step 3. Bn+1B_{n+1} creates a single exceptional overlap with BnB_n.

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

From Steps 1–3 it follows that B1∪B2∪⋯∪Bn+1={P(Y):Y⊆S}B_1 \cup B_2 \cup \cdots \cup B_{n+1} = \{P(Y) : Y \subseteq S\}, and the only non-empty pairwise intersections are Di:=Bi∩Bi+2D_i := B_i \cap B_{i+2} for i=1,…,n−1i = 1, \ldots, n-1, together with the single exceptional order ∣Bn∩Bn+1∣=1|B_n \cap B_{n+1}| = 1.

Step 4. Computing ∣Bi∣|B_i|.

The graph GiG_i consists of two directed paths (“bamboo sticks”). Since each BiB_i encodes all possible subsets YY whose source string first deviates from S\mathcal{S} at position ii, the bamboo lengths depend on the parity of ii:

  • if ii is odd: ∣Bi∣=(n(i−1)/2)|B_i| = \dbinom{n}{(i-1)/2},
  • if ii is even: ∣Bi∣=(nn−i/2+1)|B_i| = \dbinom{n}{n - i/2 + 1}.

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

∑i=1n+1∣Bi∣=2n.\sum_{i=1}^{n+1} |B_i| = 2^n.

Step 5. Computing the overlaps ∣Di∣|D_i| where Di=Bi∩Bi+2D_i = B_i \cap B_{i+2}.

From Steps 1 and 2, Di∩Dj=∅D_i \cap D_j = \varnothing for i≠ji \ne j. Consider the union graph G′G' of GiG_i and Gi+2G_{i+2}. For odd ii, the graph G′G' is almost identical to Gi+2G_{i+2} except that edges i→i+1i \to i+1 and i+1→i+2i+1 \to i+2 are added, which fix the relative order of (i+1)/2(i+1)/2 vertices. Removing these determined vertices leaves two bamboo sticks, one with (i−1)/2(i-1)/2 vertices. Hence for odd ii,

∣Di∣=(n−(i+1)/2(i−1)/2).|D_i| = \binom{n - (i+1)/2}{(i-1)/2}.
Substituting i=2h+1i = 2h+1 gives ∣Di∣=(n−1−hh)|D_i| = \binom{n-1-h}{h}.

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

Step 6. Assembling the answer.

By inclusion–exclusion,

N(n)=∑i=1n+1∣Bi∣−1−∑i=1n−1∣Di∣,N(n) = \sum_{i=1}^{n+1} |B_i| - 1 - \sum_{i=1}^{n-1} |D_i|,
where −1-1 accounts for the single exceptional overlap ∣Bn∩Bn+1∣=1|B_n \cap B_{n+1}| = 1 from Step 3.

The sum of ∣Bi∣|B_i| equals 2n2^n (Step 4).

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

In both cases the total is

∑i=1n−1∣Di∣=Fn+Fn−1−1=Fn+1−1.\sum_{i=1}^{n-1} |D_i| = F_n + F_{n-1} - 1 = F_{n+1} - 1.

Therefore,

N(n)=2n−1−(Fn+1−1)=2n−Fn+1,\boxed{N(n) = 2^n - 1 - (F_{n+1} - 1) = 2^n - F_{n+1}},
where Fn+1=Fn+Fn−1F_{n+1} = F_n + F_{n-1} is the (n+1)(n{+}1)-th Fibonacci number (with F1=F2=1F_1 = F_2 = 1).

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;