Maths Olympiad Prep

Library / /333 of 520

Combinatorics Difficulty 6.7 National olympiad Find the answer

A permutation of the set {1,,2021}\{1, \ldots, 2021\} is a sequence σ=(σ1,,σ2021)\sigma=\left(\sigma_{1}, \ldots, \sigma_{2021}\right) such that each element of the set {1,,2021}\{1, \ldots, 2021\} is equal to exactly one term σi\sigma_{i}. We define the weight of such a permutation σ\sigma as the sum

i=12020σi+1σi \sum_{i=1}^{2020}\left|\sigma_{i+1}-\sigma_{i}\right|

What is the greatest possible weight of permutations of {1,,2021}\{1, \ldots, 2021\}?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n=2021n=2021, and let σ\sigma be a permutation of {1,2,,n}\{1,2, \ldots, n\} and let W(σ)\mathbf{W}(\sigma) be its weight. For all integers knk \leqslant n, we set


k =\text{k =}
1 & \text{} { if } k n\text{n} { and } σ(k)>σ(k+1)\sigma(k)>\sigma(k+1) \\
0 & \text{} { if } k=n \\
-1 & \text{} { if } k n\text{n} { and } σ(k)σ(k1)\sigma(k)\sigma(k-1) \\
0 & \text{} { if } k=1 \\
-1 & \text{} { if } k 1\text{1} { and } σ(k)σi>σi+1\sigma(k)\sigma_{i}>\sigma_{i+1}.Wethendenoteby. We then denote by σ\sigma^{\prime}thepermutationof the permutation of {1,2,,n}$\{1,2, \ldots, n\}\$ defined by:

σj=σj when 1ji1;σj=σj+1 when ijn1;σn=σi. \begin{aligned} & \triangleright \sigma_{j}^{\prime}=\sigma_{j} \text { when } 1 \leqslant j \leqslant i-1 ; \\ & \triangleright \sigma_{j}^{\prime}=\sigma_{j+1} \text { when } i \leqslant j \leqslant n-1 ; \\ & \triangleright \sigma_{n}^{\prime}=\sigma_{i} . \end{aligned}

Since σiσi+1+σi+1σi+2=σiσi+2\left|\sigma_{i}-\sigma_{i+1}\right|+\left|\sigma_{i+1}-\sigma_{i+2}\right|=\left|\sigma_{i}-\sigma_{i+2}\right|, the weight of σ\sigma^{\prime} is that of σ\sigma plus σnσ1\left|\sigma_{n}-\sigma_{1}\right|, which contradicts the maximality of the weight of σ\sigma.
Moreover, and by replacing σ\sigma with its "horizontal mirror" permutation, i.e., by replacing each term σj\sigma_{j} with n+1σjn+1-\sigma_{j}, which does not change the weight of σ\sigma, we assume without loss of generality that σ1σ2j+1\sigma_{1}\sigma_{2 j+1} for all integers jj such that 1jk1 \leqslant j \leqslant k.
The weight of σ\sigma is then

j=1k2σ2jσ1σnj=1k12σ2j+1 \sum_{j=1}^{k} 2 \sigma_{2 j}-\sigma_{1}-\sigma_{n}-\sum_{j=1}^{k-1} 2 \sigma_{2 j+1}

Since σ\sigma does not take the same value twice, we have

j=1k2σ2jj=n+1kn2j=n(n+1)(nk)(n+1k)=3k2+3k and j=1k12σ2j+1+σ1+σnj=1k12j+k+(k+1)=k(k1)+(2k+1)=k2+k+1 \begin{aligned} & \sum_{j=1}^{k} 2 \sigma_{2 j} \leqslant \sum_{j=n+1-k}^{n} 2 j=n(n+1)-(n-k)(n+1-k)=3 k^{2}+3 k \text { and } \\ & \sum_{j=1}^{k-1} 2 \sigma_{2 j+1}+\sigma_{1}+\sigma_{n} \geqslant \sum_{j=1}^{k-1} 2 j+k+(k+1)=k(k-1)+(2 k+1)=k^{2}+k+1 \end{aligned}

Therefore, the weight of σ\sigma cannot exceed 2k2+2k1=20422192 k^{2}+2 k-1=2042219.
Conversely, the permutation indicated at the end of the previous solution is indeed of weight 2042219, and this is indeed the maximum weight.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.