Library / China Mathematical Competition /98 of 136

China Mathematical Competition

Combinatorics Difficulty 5.4 AIME, harder Prove it China

Let $a_1, a_2, \dots, a_{21}$ be a permutation of $1, 2, \dots, 21$ , satisfying
$|a_{20} - a_{21}| \geq |a_{19} - a_{21}| \geq |a_{18} - a_{21}| \geq \dots \geq |a_1 - a_{21}|.$
The number of such permutations is ________.

Solution

For a given $k \in \{1, 2, \dots, 21\}$ , consider the number of permutations $N_k$ that satisfy the conditions such that $a_{21} = k$ .
When $k \in \{1, 2, \dots, 11\}$ , for $i = 1, 2, \dots, k-1$ , there exist $a_{2i-1}, a_{2i}$ that are permutations of $k-i, k+i$ (if $k=1$ , there exists no such $i$ ), and $a_{2j} = j+1$ ( $2k-1 \le j \le 20$ ) (if $k=11$ , there exists no such $j$ ), so $N_k = 2^{k-1}$ .

Similarly, when $k \in \{12, 13, \dots, 21\}$ , there is $N_k = 2^{21-k}$ .
Therefore, the number of such permutations satisfying the condition is

$\sum_{k=1}^{21}$ N_k = $\sum_{k=1}^{11} 2^{k-1} + \sum_{k=12}^{21} 2^{21-k} = (2^{11}-1) + (2^{10}-1)$ = 3070. $\quad \square$

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.