Maths Olympiad Prep

Library / /18 of 48

Combinatorics Difficulty 5.2 AIME, harder Prove it Baltic Way

Let p1,,p30p_1, \dots, p_{30} be a permutation of numbers 1,2,,301, 2, \dots, 30. For how many permutations does the equality k=130pkk=450\sum_{k=1}^{30} |p_k - k| = 450 hold?

Solution

Answer: (15!)2(15!)^2.

Let us define pairs (ai,bi)(a_i, b_i) such that {ai,bi}={pi,i}\{a_i, b_i\} = \{p_i, i\} and aibia_i \ge b_i. Then for every i=1,,30i = 1, \dots, 30 we have pii=aibi|p_i - i| = a_i - b_i and
i=130pii=i=130(aibi)=i=130aii=130bi. \sum_{i=1}^{30} |p_i - i| = \sum_{i=1}^{30} (a_i - b_i) = \sum_{i=1}^{30} a_i - \sum_{i=1}^{30} b_i.
It is clear that the sum i=130aii=130bi\sum_{i=1}^{30} a_i - \sum_{i=1}^{30} b_i is maximal when
{a1,a2,,a30}={16,17,,30} and {b1,b2,,b30}={1,2,,15} \{a_1, a_2, \dots, a_{30}\} = \{16, 17, \dots, 30\} \text{ and } \{b_1, b_2, \dots, b_{30}\} = \{1, 2, \dots, 15\}
and the maximal value equals 2(16++30115)=4502(16 + \dots + 30 - 1 - \dots - 15) = 450. The number of such permutations is (15!)2(15!)^2.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.