Maths Olympiad Prep

Library / /207 of 520

Combinatorics Difficulty 6.0 AIME, harder Prove it

3. Let a1,a2,,ama_{1}, a_{2}, \cdots, a_{m} be mm non-negative integers. Prove:
min(a1,a2,,am)=1i1mai11i1<i2mmax(ai1,ai2)++(1)k11i1<<ikmmax(ai1,,aik)++(1)m1max(a1,,am)\begin{aligned} \min \left(a_{1}, a_{2}, \cdots, a_{m}\right)= & \sum_{1 \leqslant i_{1} \leqslant m} a_{i_{1}}-\sum_{1 \leqslant i_{1}<i_{2} \leqslant m} \max \left(a_{i_{1}}, a_{i_{2}}\right)+\cdots \\ & +(-1)^{k-1} \sum_{1 \leqslant i_{1}<\cdots<i_{k} \leqslant m} \max \left(a_{i_{1}}, \cdots, a_{i_{k}}\right) \\ & +\cdots+(-1)^{m-1} \max \left(a_{1}, \cdots, a_{m}\right) \end{aligned}

Solution

3. Take a positive integer N>max(α1,α2,,αm)N>\max \left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{m}\right). The set AA is the set of all non-negative integers not less than NN. The property Pi(1im)P_{i}(1 \leqslant i \leqslant m) is not less than aia_{i}.

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.