Let $n\geqslant 0$ be an integer, and let $a_0,a_1,\dots,a_n$ be real numbers. Show that there exists $k\in\{0,1,\dots,n\}$ such that $$a_0+a_1x+a_2x^2+\cdots+a_nx^n\leqslant a_0+a_1+\cdots+a_k$$for all real numbers $x\in[0,1]$.
Problem
Source: BxMO 2022, Problem 1
Tags: BxMO, algebra, polynomial
01.05.2022 21:33
BxMO 2022/1 wrote: Let $n\geqslant 0$ be an integer, and let $a_0,a_1,\dots,a_n$ be real numbers. Show that there exists $k\in\{0,1,\dots,n\}$ such that $$a_0+a_1x+a_2x^2+\cdots+a_nx^n\leqslant a_0+a_1+\cdots+a_k$$for all real numbers $x\in[0,1]$. Really cute. It suffices to prove that for all $x \in [0,1]$, we have \[ a_0 + a_1 x + \dots + a_n x^n \le \max_{0 \le k \le n} a_0 + \dots + a_k \]The problem is killed by the following observation: Main Claim. For any $a,b \in \mathbb{R}$ and $x \in [0,1]$, then $a + bx \le \max(a, a + b)$ Proof. Suppose otherwise, there exists $y \in [0,1]$ such that $a + by > \max(a, a + b)$. Therefore, \begin{align*} a + by &> \max(a, a + b) \ge a \implies b > 0 \\ a + by &> \max(a, a + b) \ge a + b \implies y > 1 \end{align*}which is a contradiction. We will now proceed by induction on $n$. The problem is obvious for $n = 0$ and the main claim above solves the problem for $n = 1$. Let us now suppose that the problem is true for $n = k$. Then for any $x \in [0,1]$, we have \begin{align*} a_0 + a_1 x + a_2 x^2 + \dots + a_{k + 1} x^{k + 1} &= a_0 + x(a_1+ \dots + a_k x^{k - 1} + a_{k + 1}x^{k}) \\ &\stackrel{\text{inductive hypothesis}}{\le} a_0 + x ( \max_{1 \le i \le k + 1} a_1 + \dots + a_i) \\ &\stackrel{\text{Claim}}{\le} \max(a_0, a_0 + \max_{1 \le i \le k + 1} a_1 + \dots + a_i) = \max_{0 \le i \le k + 1} a_0 + \dots + a_i \end{align*}which proves the problem for $n = k + 1$. Therefore, the original result holds true for any $n \ge 0$.
01.05.2022 22:16
Lepuslapis wrote: Let $n\geqslant 0$ be an integer, and let $a_0,a_1,\dots,a_n$ be real numbers. Show that there exists $k\in\{0,1,\dots,n\}$ such that $$a_0+a_1x+a_2x^2+\cdots+a_nx^n\leqslant a_0+a_1+\cdots+a_k$$for all real numbers $x\in[0,1]$. Another induction solution. For $n=0$, $k=0$ is only option and inequality holds since $a_0 \leq a_0$. Now suppose thy problem is true for $n=m$. So, For any real numbers $a_0, a_1, \cdots , a_m$ there exists a $k_m$ such that, $$a_0+a_1x+a_2x^2+\cdots+a_mx^m \leq a_0+a_1+...+a_{k_m}$$for all $x\in[0,1]$ So it suffices to prove for $n=m+1$. Now note that if $a_{m+1} < 0$ then, $$a_0+a_1x+ \cdots + a_mx^m + a_{m+1}x^{m+1} < a_0 + a_1x+...+ a_mx^m$$If we apply our induction hypothesis to $a_0,a_1,\cdots,a_m$ then we can find a number $k_{m}\in\{0,1,\cdots,m\}$. $k_{m+1}$ can be chosen as $k_{m+1}=k_{m}$. So, $$a_0 + a_1x+...+ a_mx^m < a_0+a_1+\cdots+a_k \Longrightarrow a_0+a_1x+ \cdots + a_mx^m + a_{m+1}x^{m+1} \leq a_0+a_1+\cdots+a_{k_{m+1}}$$For all $x\in[0,1]$ We are done in this case. Now if $a_{m+1} \geq 0$ then, $$a_0+a_1x+ \cdots + a_mx^m + a_{m+1}x^{m+1} \leq a_0+a_1x+ \cdots + a_mx^m + a_{m+1}x^{m} = a_0+a_1x+ \cdots + (a_m+a_{m+1})x^{m}$$Now if we apply our induction hypothesis for $b_0=a_0, b_1=a_1, \cdots , b_{m-1}=a_{m-1}, b_{m}=a_m+a_{m+1}$ then we can find a natural number $k_{m}\in \{0,1,\cdots,m\}$ such that, $$b_0+b_1x+\cdots+b_mx^m \leq b_0+b_1+\cdots+b_{k_m}$$Note that the set $B = \{\sum_{i=0}^{j}b_i \mid j \in \{0,1,...m\}\}$ is a subset of $A = \{\sum_{i=0}^{j}a_i \mid j \in \{0,1,...,m+1\}\}$. So $k_{m+1}$ can be chosen as, if $k_m=m$ then $k_{m+1}=m+1$ and if not then $k_{m+1}=k_m$. So we get, $$a_0+a_1x+ \cdots + a_mx^m + a_{m+1}x^{m+1} \leq a_0+a_1x+ \cdots + (a_m+a_{m+1})x^{m} = b_0+b_1x+\cdots+b_mx^m \leq b_0+b_1+\cdots+b_{k_m} = a_0+a_1+\cdots+a_{k_{m+1}}$$So for $n=m+1$ we can also find a number $k_{m+1}$ that satisfies our condition. Hence the problem is true for any $n\geq0$.