Let $n$ be a positive integer and $a_1,a_2,\ldots a_{2n+1}$ be positive reals. For $k=1,2,\ldots ,2n+1$, denote $b_k = \max_{0\le m\le n}\left(\frac{1}{2m+1} \sum_{i=k-m}^{k+m} a_i \right)$, where indices are taken modulo $2n+1$. Prove that the number of indices $k$ satisfying $b_k\ge 1$ does not exceed $2\sum_{i=1}^{2n+1} a_i$.
Problem
Source: China TST 2021, Test 2, Day 2 P5
Tags: inequalities, algebra, combinatorics
05.04.2021 12:39
Any solutions?
09.04.2021 23:26
Call an interval of the form $a_{i-k},...,a_{i+k}$ bad if $a_{i-k}+...+a_{i+k}\ge 2k+1$ and paint each number that belongs to at least one bad interval red. Clearly there is no bad interval of length more than $n$ else we would be over with thus two bad intervals don't intersect in both ends. The set of red numbers is covered by the the set $B$ of bad intervals (needless to say the indices the problem asks about are among the red numbers). There is a subcover $S\subset B$ of all the red indices such that no number is covered by more than two intervals. Proof : Consider the minimal subcover of the red numbers , if there is an index $c$ that is covered by at least three intervals say $[i_1,j_1],[i_2,j_2],[i_3,j_3]$ and $i_1\le i_2 \le i_3\le c \le j_1,j_2,j_3$ then we can remove one of $[i,j]$ to get a smaller subcover. One of $j_2,j_3$ is not strictly maximal among $j_{1,2,3}$ so remove the corresponding interval. Then because each $a_i$ will be counted at most twice $(red numbers)\le \sum_{[i,j]\in S} length([i,j])\le \sum_{[i,j]\in S}(a_i+...+a_j)\le 2(a_1+...+a_{2n+1})$ .
06.01.2022 23:32
Let $S = \{k : b_k \ge 1 \}$. For each $k$, choose a $f(k) \in \{0,\ldots,n\}$ satisfying $$b_k = \frac{1}{1 + 2f(k)} \cdot \sum_{i = k - f(k)}^{k + f(k)} a_i$$Further, for any $k$, define the sets (intuitively, the letter $\mathcal C$ denotes cover and $\mathcal R$ denotes range): $$\mathcal C(k) = \{k - f(k),\ldots,k + f(k) \} \qquad , \qquad \mathcal R(k) = \{k - 2f(k),\ldots,k + 2f(k) \}$$If $S$ is non-empty, then we are done. Otherwise, choose a $\delta_1 \in S$ such that $$f(\delta_1) = \max \{f(x): x \in S \}$$Now having chosen $\delta_1,\ldots,\delta_j$, we define $$X_j = \{x : x \in S \text{ but } x \notin \mathcal R(\delta_1),\ldots,\mathcal R(\delta_j) \}$$Now if $X_j$ is non-empty, then we choose a $\delta_{j+1} \in X_j$ such that $$f(\delta_{j+1}) = \max \{f(x) : x \in X_j \}$$Note that this process must stop as all $\delta_i$s are distinct by definition and $S$ is finite. Suppose we obtain $\delta_1,\ldots,\delta_t$ in this way (so $|X_t| = 0$ now by definition). Claim: For any $i,j$, the sets $\mathcal C(\delta_i),\mathcal C( \delta_j)$ are disjoint. Proof: WLOG, $i < j$. Just use $f(\delta_i) \ge f(\delta_j)$ and $\delta_j \notin \mathcal R(\delta_i)$ (both of which are true just by definition). $\square$ Using our claim we obtain $$\sum_{i=1}^{2n+1} a_i \ge \sum_{j=1}^t \left( \sum_{a_i \in \mathcal C (\delta_i)} a_i \right) \ge \sum_{j=1}^t |\mathcal C(\delta_i)| = \sum_{j=1}^t (2 f(\delta_i) + 1) \qquad \qquad (1)$$Now since $|X_t| = 0$, so we must have $$S \subseteq \cup_{i=1}^t \mathcal R(\delta_i)$$But the cardinality of the set on RHS is at most $$\sum_{i=1}^t |\mathcal R(\delta_i)| = \sum_{i=1}^t (4 \delta_i + 1)$$So we conclude that $$|S| \le \sum_{i=1}^t (4 f(\delta_i) + 1)$$By combining this with $(1)$, our problem follows. $\blacksquare$ Remark: This proof shows that the bound can be strengthened to $$\left(2 \sum_{i=1}^{2n+1} a_i \right) - 1$$whenever at least one $b_k$ is $\ge 1$.
07.01.2022 09:44
Beautiful
08.01.2022 19:08
This is a discrete version of Hardy-Littlewood maximal function. It does not matter that the family of indices the average is taken over is centered. The same claim is true if we take the max average with respect to any contiguous set of indices that contains $ k$. Further, it holds $$\#\{k: b_k\ge \alpha\}\le \frac{2}{\alpha}\sum_{i=1}^{2n+1}a_i.$$We can also improve it slightly $$\#\{k: b_k\ge \alpha\}\le \frac{2}{\alpha}\sum_{i:b_i\ge \alpha}a_i.$$If the average is taken over all contiguous sets of indices with left (right) end at $k$ then we can put a constant $1$ instead of $2$. One can see also some similar problems: USA TSTST 2015,p1; ARO 2000, p11.4.