IMC 2026, Ημέρα 1, Θέμα 3
Consider a deck of cards labeled . 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 , the first stack is , and the second stack is . Then the order resulting from the alternating shuffle is .
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Daniel Volostnov, Neapolis University Paphos, Cyprus)
Solution. Setup. Define the reference string of length . For a given subset of cards in the first stack, let be the source string of : if the card at position of came from deck , and otherwise.
For , define
For each , let be the directed graph on vertex set where there is an edge from to whenever , encoding the relative-order structure common to all orders of .
Throughout, assume .
Step 1. whenever is odd.
Consider the graphs and , and look at vertices and . For and of different parity, the edge between and is directed in opposite ways in and . If a common order existed in , it would simultaneously require and , a contradiction.
Step 2. whenever is even and .
Consider the graphs and at vertices and . By the same argument as in Step 1, the edges between these vertices point in opposite directions, giving a contradiction.
Step 3. creates a single exceptional overlap with .
The set is on equal footing with the other : Steps 1 and 2 apply to it as well, so is disjoint from all except possibly and (by parity). In fact, and share exactly one order: the sequence produced by and . This is because the edge does not appear in , so the graph constraint of is also satisfied. No other order of lies in .
From Steps 1–3 it follows that , and the only non-empty pairwise intersections are for , together with the single exceptional order .
Step 4. Computing .
The graph consists of two directed paths (“bamboo sticks”). Since each encodes all possible subsets whose source string first deviates from at position , the bamboo lengths depend on the parity of :
- if is odd: ,
- if is even: .
Since all together (for ) partition the set of source-string encodings of all subsets, we have
Step 5. Computing the overlaps where .
From Steps 1 and 2, for . Consider the union graph of and . For odd , the graph is almost identical to except that edges and are added, which fix the relative order of vertices. Removing these determined vertices leaves two bamboo sticks, one with vertices. Hence for odd ,
An analogous argument for even yields .
Step 6. Assembling the answer.
By inclusion–exclusion,
The sum of equals (Step 4).
The sum over odd-indexed : when is odd this equals ; when is even this equals . Similarly, the sum over even-indexed : when is odd this equals ; when is even this equals .
In both cases the total is
Therefore,
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.