Maths Olympiad Prep

Library / /21 of 48

Combinatorics Difficulty 8.4 Shortlist Prove it China

Let nn be a positive integer, a1,a2,,a2n+1a_1, a_2, \dots, a_{2n+1} be 2n+12n+1 positive real numbers. For k=1,2,,2n+1k = 1, 2, \dots, 2n+1, define
bk=max0mn(12m+1i=kmk+mai), b_k = \max_{0 \le m \le n} \left( \frac{1}{2m+1} \sum_{i=k-m}^{k+m} a_i \right),
where the subscript of aia_i is taken modulo 2n+12n+1. Prove: the number of subscripts kk satisfying that bk1b_k \ge 1 does not exceed 2i=12n+1ai2 \sum_{i=1}^{2n+1} a_i.

Solution

Define I={kbk1}I = \{k \mid b_k \ge 1\}. For every kIk \in I, assume that the maximum value bkb_k of 12m+1i=kmk+mai\frac{1}{2m+1} \sum_{i=k-m}^{k+m} a_i is attained at m=mkm = m_k, and call
[kmk,k+mk]:={kmk,kmk+1,,k+mk} [k - m_k, k + m_k] := \{k - m_k, k - m_k + 1, \dots, k + m_k\}
a “nice segment”, where the subscripts are taken modulo 2n+12n+1. Obviously, the union of all nice segments contains II.

Claim There exists a collection of nice segments whose union contains II, and moreover, each i{1,2,,2n+1}i \in \{1, 2, \dots, 2n + 1\} is contained in at most two segments.

Proof of claim If [1,2n+1][1, 2n + 1] is a nice segment, the conclusion is trivial. In the following, assume this is not the case. If ii is contained in rr nice segments
[iu1,i+v1],,[iur,i+vr] [i - u_1, i + v_1], \dots, [i - u_r, i + v_r]
where r3r \ge 3 and 0uj,vj<2n0 \le u_j, v_j < 2n, let uj=max{u1,,ur}u_j = \max\{u_1, \dots, u_r\} and vk=max{v1,,vr}v_k = \max\{v_1, \dots, v_r\}. We can keep the nice segments [iuj,i+vj][i - u_j, i + v_j], [iuk,i+vk][i - u_k, i + v_k] and drop the other r2r-2 segments. Now the segments still cover 1,,2n+11, \dots, 2n+1, and at most two of them cover ii. For each i{1,2,,2n+1}i \in \{1, 2, \dots, 2n+1\}, perform the above operation. Eventually, we find a collection of nice segments with the desired properties.

For the original problem, let [i1m1,i1+m1][i_1 - m_1, i_1 + m_1], \dots, [irmr,ir+mr][i_r - m_r, i_r + m_r] be a collection of nice segments chosen in the claim. We have
2i=12n+1aiα=1rk=iαmαiα+mαak=α=1r(2mα+1)biαα=1r(2mα+1)I, 2 \sum_{i=1}^{2n+1} a_i \ge \sum_{\alpha=1}^{r} \sum_{k=i_{\alpha}-m_{\alpha}}^{i_{\alpha}+m_{\alpha}} a_k = \sum_{\alpha=1}^{r} (2m_{\alpha} + 1)b_{i_{\alpha}} \ge \sum_{\alpha=1}^{r} (2m_{\alpha} + 1) \ge |I|,
the first inequality is due to each ii being contained in at most two nice segments; the equality and the next inequality are due to the definition of nice segments; the last inequality is due to the union of the nice segments containing II. \square

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.