Maths Olympiad Prep

Library / /839 of 860

Algebra Difficulty 5.7 AIME, harder Find the answer

Suppose that (a1,,a20)(a_{1}, \ldots, a_{20}) and (b1,,b20)(b_{1}, \ldots, b_{20}) are two sequences of integers such that the sequence (a1,,a20,b1,,b20)(a_{1}, \ldots, a_{20}, b_{1}, \ldots, b_{20}) contains each of the numbers 1,,401, \ldots, 40 exactly once. What is the maximum possible value of the sum i=120j=120min(ai,bj)\sum_{i=1}^{20} \sum_{j=1}^{20} \min (a_{i}, b_{j})?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let xkx_{k}, for 1k401 \leq k \leq 40, be the number of integers ii with 1i201 \leq i \leq 20 such that aika_{i} \geq k. Let yky_{k}, for 1k401 \leq k \leq 40, be the number of integers jj with 1j201 \leq j \leq 20 such that bjkb_{j} \geq k. It follows from the problem statement that xk+ykx_{k}+y_{k} is the number of elements of the set {1,,40}\{1, \ldots, 40\} which are greater than or equal to 40, which is just 41k41-k. Note that if 1i,j201 \leq i, j \leq 20, and 1k401 \leq k \leq 40, then min(ai,bj)k\min (a_{i}, b_{j}) \geq k if and only if aika_{i} \geq k and bjkb_{j} \geq k. So for a fixed kk with 1k401 \leq k \leq 40, the number of pairs (i,j)(i, j) with 1i,j201 \leq i, j \leq 20 such that min(ai,bj)k\min (a_{i}, b_{j}) \geq k is equal to xkykx_{k} y_{k}. So we can rewrite i=120j=120min(ai,bj)=k=140xkyk\sum_{i=1}^{20} \sum_{j=1}^{20} \min (a_{i}, b_{j})=\sum_{k=1}^{40} x_{k} y_{k}. Since xk+yk=41kx_{k}+y_{k}=41-k for 1k401 \leq k \leq 40, we have xkyk41k241k2x_{k} y_{k} \leq\left\lfloor\frac{41-k}{2}\right\rfloor\left\lceil\frac{41-k}{2}\right\rceil by a convexity argument. So i=120j=120min(ai,bj)k=14041k241k2=5530\sum_{i=1}^{20} \sum_{j=1}^{20} \min (a_{i}, b_{j}) \leq \sum_{k=1}^{40}\left\lfloor\frac{41-k}{2}\right\rfloor\left\lceil\frac{41-k}{2}\right\rceil=5530. Equality holds when (a1,,a20)=(2,4,,38,40)(a_{1}, \ldots, a_{20})=(2,4, \ldots, 38,40) and (b1,,b20)=(1,3,,37,39)(b_{1}, \ldots, b_{20})=(1,3, \ldots, 37,39).

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