Maths Olympiad Prep

Library / /32 of 63

Combinatorics Difficulty 6.9 National olympiad Prove it Japan

How many permutations p1,p2,,p2023p_1, p_2, \dots, p_{2023} of 1,2,,20231, 2, \dots, 2023 satisfy the equation
p1+p2p1+p3p2++p2023p2022+p2023=4048? p_1 + |p_2 - p_1| + |p_3 - p_2| + \dots + |p_{2023} - p_{2022}| + p_{2023} = 4048?

Solution

Let p0=p2024=0p_0 = p_{2024} = 0 and let tt be a positive integer such that pt=2023p_t = 2023. The given condition gives
2=4048(2023+2023)=(p1+i=12022pi+1pi+p2023)(i=0t1(pi+1pi)+i=t2023(pipi+1))=(i=0t1pi+1pi+i=t2023pipi+1)(i=0t1(pi+1pi)+i=t2023(pipi+1))=i=0t1(pi+1pi(pi+1pi))+i=t2023(pipi+1(pipi+1)), \begin{aligned} & 2 = 4048 - (2023 + 2023) \\ &= \left( p_1 + \sum_{i=1}^{2022} |p_{i+1} - p_i| + p_{2023} \right) - \left( \sum_{i=0}^{t-1} (p_{i+1} - p_i) + \sum_{i=t}^{2023} (p_i - p_{i+1}) \right) \\ &= \left( \sum_{i=0}^{t-1} |p_{i+1} - p_i| + \sum_{i=t}^{2023} |p_i - p_{i+1}| \right) - \left( \sum_{i=0}^{t-1} (p_{i+1} - p_i) + \sum_{i=t}^{2023} (p_i - p_{i+1}) \right) \\ &= \sum_{i=0}^{t-1} \left( |p_{i+1} - p_i| - (p_{i+1} - p_i) \right) + \sum_{i=t}^{2023} \left( |p_i - p_{i+1}| - (p_i - p_{i+1}) \right), \end{aligned}
thus
f(i)={pi+1pi(0it1),pipi+1(ti2023) f(i) = \begin{cases} p_{i+1} - p_i & (0 \le i \le t-1), \\ p_i - p_{i+1} & (t \le i \le 2023) \end{cases}
satisfies i=02023(f(i)f(i))=2\sum_{i=0}^{2023} (|f(i)| - f(i)) = 2. Since we have
aa={0(a0),2a(a<0) |a| - a = \begin{cases} 0 & (a \ge 0), \\ 2|a| & (a < 0) \end{cases}
for any integer aa, i=02023(f(i)f(i))=2\sum_{i=0}^{2023} (|f(i)| - f(i)) = 2 if and only if there exists an integer kk with 0k20230 \le k \le 2023 such that f(k)=1f(k) = -1 and f(i)>0f(i) > 0 for every integer ii which is different from kk and 0i20230 \le i \le 2023. Since f(0)f(0), f(t1)f(t-1), f(t)f(t) and f(2023)f(2023) are all positive, kk is neither 00, t1t-1, tt nor 20232023.

When kt+1k \ge t+1, we have 0=p0<p1<<pt>pt+1>>pk<pk+1>pk+2>>p2024=00 = p_0 < p_1 < \dots < p_t > p_{t+1} > \dots > p_k < p_{k+1} > p_{k+2} > \dots > p_{2024} = 0 with pk+1=pk+1p_{k+1} = p_k + 1. Since pk+1<2023p_{k+1} < 2023, we have pk=pk+112021p_k = p_{k+1} - 1 \le 2021. Let (A,B)(A, B) be a pair of sets satisfying AB=A \cap B = \emptyset, AB={1,2,,m1,m+2,m+3,,2022}A \cup B = \{1, 2, \dots, m-1, m+2, m+3, \dots, 2022\} for some integer mm with 1m20211 \le m \le 2021. We fix such a pair (A,B)(A, B), and consider all permutations p1,p2,,p2023p_1, p_2, \dots, p_{2023} that satisfy the following conditions:
{p1,p2,,pt1}=A, \bullet \{p_1, p_2, \dots, p_{t-1}\} = A,
pt=2023, pk=m, pk+1=m+1, \bullet p_t = 2023,\ p_k = m,\ p_{k+1} = m+1,
{pt+1,pt+2,,pk1,pk+2,pk+3,,p2023}=B \bullet \{p_{t+1}, p_{t+2}, \dots, p_{k-1}, p_{k+2}, p_{k+3}, \dots, p_{2023}\} = B
The number of such permutations is to be determined. Note that p1,p2,,pt1p_1, p_2, \dots, p_{t-1} are arranged in increasing order of elements in AA. The numbers pt+1,pt+2,,pk1p_{t+1}, p_{t+2}, \dots, p_{k-1} are arranged in decreasing order of the elements in BB that are greater than mm, and the numbers pk+2,pk+3,,p2023p_{k+2}, p_{k+3}, \dots, p_{2023} are arranged in decreasing order of the elements in BB that are less than m+1m+1. Therefore, pt+1,pt+2,,pk1,pk+2,pk+3,,p2023p_{t+1}, p_{t+2}, \dots, p_{k-1}, p_{k+2}, p_{k+3}, \dots, p_{2023} are arranged in decreasing order of elements in BB. Conversely, this permutation satisfies all the conditions, hence we conclude that there is exactly one such permutation. Since there are 20212021 choices for mm, and 220202^{2020} choices for (A,B)(A, B), there are 2021220202021 \cdot 2^{2020} permutations satisfying the conditions when kt+1k \ge t+1.

By the same reasoning, the number of permutations satisfying the conditions when kt2k \le t-2 is also 2021220202021 \cdot 2^{2020}. Thus, the answer is 2021220202=2021220212021 \cdot 2^{2020} \cdot 2 = 2021 \cdot 2^{2021}.

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.