Maths Olympiad Prep

Library / /488 of 520

Algebra Difficulty 7.3 National olympiad, round 2 Prove it

Example 6 Let a1,a2,,ama_{1}, a_{2}, \cdots, a_{m} be mm non-negative integers, then the maximum value among them is
max(a1,a2,,am)=1i1mai11i1<i2mmin(ai1,ai2)++(1)k11i1<<ikmmin(ai1,,aik)++(1)m1min(a1,,am)\begin{aligned} \max \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} \min \left(a_{i_{1}}, a_{i_{2}}\right)+\cdots \\ & +(-1)^{k-1} \sum_{1 \leqslant i_{1}<\cdots<i_{k} \leqslant m} \min \left(a_{i_{1}}, \cdots, a_{i_{k}}\right) \\ & +\cdots+(-1)^{m-1} \min \left(a_{1}, \cdots, a_{m}\right) \end{aligned}

Solution

Let NN be a positive integer not less than all aj(1jm)a_{j}(1 \leqslant j \leqslant m). In Theorem 7, take the sequence AA to be 1,2,,N1,2, \cdots, N, and let property PjP_{j} be not greater than aj(1jm)a_{j}(1 \leqslant j \leqslant m). Thus, we have
A(i1,,ik)=min(ai1,,aik)1i1<<ikm,1km\begin{array}{c} \left|A\left(i_{1}, \cdots, i_{k}\right)\right|=\min \left(a_{i_{1}}, \cdots, a_{i_{k}}\right) \\ 1 \leqslant i_{1}<\cdots<i_{k} \leqslant m, \quad 1 \leqslant k \leqslant m \end{array}

From this and Theorem 7, it follows that the number of elements in 1,2,,N1,2, \cdots, N for which no property PjP_{j} holds, i.e., the number of elements greater than max(a1,,am)\max \left(a_{1}, \cdots, a_{m}\right), can be expressed as
N1i1mai1+1i1<i2mmin(ai1,ai2)+(1)k1i1<<ik<mmin(ai1,,aik)++(1)mmin(a1,,am)\begin{aligned} N & -\sum_{1 \leqslant i_{1} \leqslant m} a_{i_{1}}+\sum_{1 \leqslant i_{1}<i_{2} \leqslant m} \min \left(a_{i_{1}}, a_{i_{2}}\right)-\cdots \\ & +(-1)^{k} \sum_{1 \leqslant i_{1}<\cdots<i_{k}<m} \min \left(a_{i_{1}}, \cdots, a_{i_{k}}\right)+\cdots \\ & +(-1)^{m} \min \left(a_{1}, \cdots, a_{m}\right) \end{aligned}

However, the number of such elements is clearly equal to Nmax(a1,,am)N-\max \left(a_{1}, \cdots, a_{m}\right). From this and the above expression, the desired conclusion follows.

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.