Let $x_0,\dots,x_{2017}$ are positive integers and $x_{2017}\geq\dots\geq x_0=1$ such that $A=\{x_1,\dots,x_{2017}\}$ consists of exactly $25$ different numbers. Prove that $\sum_{i=2}^{2017}(x_i-x_{i-2})x_i\geq 623$, and find the number of sequences that holds the case of equality.
Problem
Source:
Tags: algebra, inequalities
25.01.2018 21:09
28.01.2018 22:08
Unless i'm missing something,I think that the minimum should be $621$ because of the sequence: $1,2,2,...,2,3,3,...,3,.....,24,24,24,25$ where $1$ and $25$ appear $1$ time,each number from $2$ to $23$ appears $87$ times and $24$ appears $102$ times.
29.01.2018 16:09
Now it is correct.
28.12.2021 20:31
31.07.2024 00:31
Denote $x_{k_i}$ as $x_{k_i}>x_{k_i-1}$ and $x_{k_1}<...<x_{k_{24}}$. We can assume $x_{k_i}=i+1$ since $\sum{x_i(x_i-x_{i-2})}$ doesn't increase. \[\sum{x_i(x_i-x_{i-2})=\sum{x_i(x_i-x_{i-1}})+\sum{x_i(x_{i-1}-x_{i-2})}}=\sum{x_{k_i}}+\sum{x_i(x_{i-1}-x_{i-2})}=324+\sum{x_i(x_{i-1}-x_{i-2})}\]Hence we want to show that $\sum{x_i(x_{i-1}-x_{i-2})}\geq 299$. Note that if $x_{k_j}\neq x_{2017},$ then there exists $x_{k_j+1}(x_{k_j}-x_{k_j-1})=x_{k_j+1}$ in the sum. Thus, for $1\leq j\leq 23$ \[\sum{x_i(x_{i-1}-x_{i-2})}\geq \sum{x_{k_{j}+1}}\geq \sum{x_{k_j}}=2+...+24=299\]which proves the lower bound. Equality occurs if and only if $\sum{x_i(x_{i-1}-x_{i-2})}=299$. Hence we must have $x_{k_j+1}=x_{k_j}$ and $x_{k_{24}}=x_{2017}$ and $x_{2017}=25,\ x_{2016}=24$. We have $2015$ gaps to fill with numbers between $2$ and $24$ by using at least twice in increasing order. Let $i$ be used in $2+t_i$ places. The number of sequences is the number of solutions of the equation $t_1+(2+t_2)+...+(2+t_{24})=2015\iff t_1+...+t_{24}=1969$ where $t_i\geq 0$. This equation has $\binom{1992}{23}$ solutions as desired.$\blacksquare$