Maths Olympiad Prep

Library / /104 of 106

Combinatorics Difficulty 9.1 IMO level Prove it IMO

The Bank of Oslo issues coins made out of two types of metal: aluminium (denoted AA) and copper (denoted CC). Morgane has nn aluminium coins, and nn copper coins, and arranges her 2n2n coins in a row in some arbitrary initial order. Given a fixed positive integer k2nk \leqslant 2n, she repeatedly performs the following operation: identify the largest subsequence containing the kk-th coin from the left which consists of consecutive coins made of the same metal, and move all coins in that subsequence to the left end of the row. For example, if n=4n=4 and k=4k=4, the process starting from the configuration AACCCACAA A C C C A C A would be
AACCCACACCCAAACAAAACCCCACCCCAAAA. A A C C C A C A \rightarrow C C C A A A C A \rightarrow A A A C C C C A \rightarrow C C C C A A A A \rightarrow \cdots .
Find all pairs (n,k)(n, k) with 1k2n1 \leqslant k \leqslant 2n such that for every initial configuration, at some point of the process there will be at most one aluminium coin adjacent to a copper coin.

Solution

Define a block to be a maximal subsequence of consecutive coins made out of the same metal, and let MbM^{b} denote a block of bb coins of metal MM. The property that there is at most one aluminium coin adjacent to a copper coin is clearly equivalent to the configuration having two blocks, one consisting of all AA-s and one consisting of all CC-s.

First, notice that if k<nk < n, the sequence An1Cn1ACA^{n-1} C^{n-1} A C remains fixed under the operation, and will therefore always have 4 blocks. Next, if k>3n+12k > \frac{3n+1}{2}, let a=kn1a = k - n - 1, b=2nk+1b = 2n - k + 1. Then k>2a+bk > 2a + b, k>2b+ak > 2b + a, so the configuration AaCbAbCaA^{a} C^{b} A^{b} C^{a} will always have four blocks:
AaCbAbCaCaAaCbAbAbCaAaCbCbAbCaAaAaCbAbCa A^{a} C^{b} A^{b} C^{a} \rightarrow C^{a} A^{a} C^{b} A^{b} \rightarrow A^{b} C^{a} A^{a} C^{b} \rightarrow C^{b} A^{b} C^{a} A^{a} \rightarrow A^{a} C^{b} A^{b} C^{a} \rightarrow \ldots
Therefore a pair (n,k)(n, k) can have the desired property only if nk3n+12n \leqslant k \leqslant \frac{3n+1}{2}. We claim that all such pairs in fact do have the desired property. Clearly, the number of blocks in a configuration cannot increase, so whenever the operation is applied, it either decreases or remains constant. We show that unless there are only two blocks, after a finite amount of steps the number of blocks will decrease.

Consider an arbitrary configuration with c3c \geqslant 3 blocks. We note that as knk \geqslant n, the leftmost block cannot be moved, because in this case all nn coins of one type are in the leftmost block, meaning there are only two blocks. If a block which is not the leftmost or rightmost block is moved, its neighbor blocks will be merged, causing the number of blocks to decrease.

Hence the only case in which the number of blocks does not decrease in the next step is if the rightmost block is moved. If cc is odd, the leftmost and the rightmost blocks are made of the same metal, so this would merge two blocks. Hence c4c \geqslant 4 must be even. Suppose there is a configuration of cc blocks with the ii-th block having size aia_{i} so that the operation always moves the rightmost block:
Aa1Aac1CacCacAa1Aac1Aac1CacAa1Cac2 A^{a_{1}} \ldots A^{a_{c-1}} C^{a_{c}} \rightarrow C^{a_{c}} A^{a_{1}} \ldots A^{a_{c-1}} \rightarrow A^{a_{c-1}} C^{a_{c}} A^{a_{1}} \ldots C^{a_{c-2}} \rightarrow \ldots
Because the rightmost block is always moved, k2n+1aik \geqslant 2n+1-a_{i} for all ii. Because ai=2n\sum a_{i} = 2n, summing this over all ii we get ck2cn+cai=2cn+c2nc k \geqslant 2c n + c - \sum a_{i} = 2c n + c - 2n, so k2n+12nc3n2+1k \geqslant 2n + 1 - \frac{2n}{c} \geqslant \frac{3n}{2} + 1. But this contradicts k3n+12k \leqslant \frac{3n+1}{2}. Hence at some point the operation will not move the rightmost block, meaning that the number of blocks will decrease, as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.