Maths Olympiad Prep

Library / HMMT November /384 of 672

HMMT November

Algebra Difficulty 5.0 AIME, harder Find the answer

Given positive integers a1,a2,…,a2023a_{1}, a_{2}, \ldots, a_{2023} such that ak=∑i=12023∣ak−ai∣a_{k}=\sum_{i=1}^{2023}\left|a_{k}-a_{i}\right| for all 1≤k≤20231 \leq k \leq 2023, find the minimum possible value of a1+a2+⋯+a2023a_{1}+a_{2}+\cdots+a_{2023}.

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

Solution

Without loss of generality, let a1≤a2≤⋯≤a2023a_{1} \leq a_{2} \leq \cdots \leq a_{2023}. Then, note that ak+1−ak=∑i=12023∣ak+1−ai∣−∣ak−ai∣=k(ak+1−ak)−(2023−k)(ak+1−ak)=(2k−2023)(ak+1−ak)a_{k+1}-a_{k}=\sum_{i=1}^{2023}\left|a_{k+1}-a_{i}\right|-\left|a_{k}-a_{i}\right|=k(a_{k+1}-a_{k})-(2023-k)(a_{k+1}-a_{k})=(2k-2023)(a_{k+1}-a_{k}). Thus, ak+1=aka_{k+1}=a_{k} unless k=1012k=1012, so a1=a2=⋯=a1012a_{1}=a_{2}=\cdots=a_{1012} and a1013=⋯=a2023a_{1013}=\cdots=a_{2023}, and we can check that that they must be in a ratio of 1011:10121011:1012. Thus, a1,…,a2023a_{1}, \ldots, a_{2023} must consist of 1012 copies of 1011c1011c, and 1011 copies of 1012c1012c for some cc, so for everything to be a positive integer, we need c≥1c \geq 1. This gives us the final answer of 1011⋅1012+1012⋅1011=20462641011 \cdot 1012+1012 \cdot 1011=2046264.

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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.