给定正整数 $n$，设 $a_1 , a_2 , \ldots , a_n$ 是非负整数序列，若其中连续若干项（可以只有一项）的算术平均值不小于 $1$，则称这些项组成一条"龙"，其中第一项称为"龙头"，最后一项称为"龙尾"．
已知 $a_1 , a_2 , \ldots , a_n$ 中每一项都是"龙头"或者"龙尾"，求 $\displaystyle \sum\limits_{i=1}^{n}a_i$ 的最小值．
已知 $a_1 , a_2 , \ldots , a_n$ 中每一项都是"龙头"或者"龙尾"，求 $\displaystyle \sum\limits_{i=1}^{n}a_i$ 的最小值．
【难度】
【出处】
2014年中国西部数学邀请赛试题
【标注】
【答案】
略
【解析】
$\displaystyle \sum\limits_{i=1}^{n}a_i$ 的最小值为 $\left[\dfrac{n}{2}\right]+1$．
首先给出构造：$n=2k-1$ 时，令 $a_k=k$，其他项为 $0$；
$n=2k$ 时，令 $a_k = k$，$a_{2k}=1$，其他项为 $0$．
容易验证此时数列中每一项郁是"龙头"或者"龙尾"，且 $\displaystyle \sum\limits_{i=1}^{n}a_i =\left[\frac{n}{2}\right]+1$．
下面用数学归纳法证明对满足要求的数列 $a_1 , a_2 , \ldots , a_n$，都有 $\displaystyle \sum\limits_{i=1}^{n}a\geqslant \left[\frac{n}{2}\right]+1$．
当 $n=1$ 时结论显然成立．假设结论对所有小于 $n$ 项的数列成立，考虑 $n$ 项的数列 $a_1 , a_2 , \ldots , a_n$，其中每一项都是"龙头"或"龙尾"．
设以 $a_1$ 为"龙头"的最长"龙"有 $t$ 项，若 $t\geqslant \left[\dfrac{n}{2}\right]+1$，则结论成立；
若 $t\leqslant\left[\dfrac{n}{2}\right]$，由 $a_1 , a_2 , \ldots , a_t$ 是最长的"龙"可知 $a_1 + a_2 + \ldots +a_t = t$ 且 $a_{t+1}=0$，
令 $b_1 = a_{t+1}+ a_{t+2}+\ldots+a_{2t},b_2 = a_{2t+1},b_3 = a_{2t+2},\ldots,b_{n-2t+1}=a_n$．
下证在数列 $b_1 , b_2 , \ldots , b_{n-2t+1}$ 中，对 $1\leqslant i\leqslant n-2t+1$，$b_i$ 都是"龙头"或"龙尾"．
若 $a_{i+2t-1}$ 是"龙头"，则 $b_i$ 也是龙头；
若 $a_{i+2t-1}$ 是"龙尾"，则存在正整数 $m$ 使得 $a_m + a_{m+1} +\ldots +a_{i+2t-1}\geqslant i+2t-m$，
对 $m$ 的值分类讨论：
（a）当 $m\geqslant 2t+1$ 时，
有 $\begin{aligned} b_{m-2 t+1}+b_{m-2 t+2}+\ldots+b_{i} &=a_{m}+a_{m+1}+\ldots+a_{i+2 t-1} \geqslant i+2 t-m \end{aligned}$ 于是 $b_i$ 是"龙尾"；
（b）当 $t+1\leqslant m\leqslant 2t$ 时，
有 $
b_{1}+b_{2}+\ldots+b_{i} \geqslant a_{m}+a_{m+1}+\ldots+a_{i+2 t-1} \geqslant i+2 t-m \geqslant i
$ 可得 $b_i$ 是"龙尾"；
（c）当 $m\leqslant t$ 时，有 $\begin{aligned} b_{1}+b_{2}+\ldots+b_{i} &=a_{1}+a_{2}+\ldots+a_{i+2t-1}-t \geqslant i+2 t-m-t \geqslant i \end{aligned}$ 同样可得 $b_i$ 也是"龙尾"．
因此，在数列 $b_1 , b_2 , \ldots , b_{n-2t+1}$ 中由归纳假设，有 $\displaystyle \sum\limits_{i=1}^{n-2t+1}b_i \geqslant \left[\frac{n-2t+1}{2}\right]+1$，
故 $\displaystyle
\sum\limits_{i=1}^{n} a_{i}=t+\sum_{i=1}^{n-2 t+1} b_{i} \geqslant t+\left[\frac{n-2 t+1}{2}\right]+1 \geqslant\left[\frac{n}{2}\right]+1
$ 结论对 $n$ 项数列也成立．
综上可知，$\displaystyle \sum\limits_{i=1}^{n}a_i$ 的最小值为 $\left[\dfrac{n}{2}\right]+1$．
首先给出构造：$n=2k-1$ 时，令 $a_k=k$，其他项为 $0$；
$n=2k$ 时，令 $a_k = k$，$a_{2k}=1$，其他项为 $0$．
容易验证此时数列中每一项郁是"龙头"或者"龙尾"，且 $\displaystyle \sum\limits_{i=1}^{n}a_i =\left[\frac{n}{2}\right]+1$．
下面用数学归纳法证明对满足要求的数列 $a_1 , a_2 , \ldots , a_n$，都有 $\displaystyle \sum\limits_{i=1}^{n}a\geqslant \left[\frac{n}{2}\right]+1$．
当 $n=1$ 时结论显然成立．假设结论对所有小于 $n$ 项的数列成立，考虑 $n$ 项的数列 $a_1 , a_2 , \ldots , a_n$，其中每一项都是"龙头"或"龙尾"．
设以 $a_1$ 为"龙头"的最长"龙"有 $t$ 项，若 $t\geqslant \left[\dfrac{n}{2}\right]+1$，则结论成立；
若 $t\leqslant\left[\dfrac{n}{2}\right]$，由 $a_1 , a_2 , \ldots , a_t$ 是最长的"龙"可知 $a_1 + a_2 + \ldots +a_t = t$ 且 $a_{t+1}=0$，
令 $b_1 = a_{t+1}+ a_{t+2}+\ldots+a_{2t},b_2 = a_{2t+1},b_3 = a_{2t+2},\ldots,b_{n-2t+1}=a_n$．
下证在数列 $b_1 , b_2 , \ldots , b_{n-2t+1}$ 中，对 $1\leqslant i\leqslant n-2t+1$，$b_i$ 都是"龙头"或"龙尾"．
若 $a_{i+2t-1}$ 是"龙头"，则 $b_i$ 也是龙头；
若 $a_{i+2t-1}$ 是"龙尾"，则存在正整数 $m$ 使得 $a_m + a_{m+1} +\ldots +a_{i+2t-1}\geqslant i+2t-m$，
对 $m$ 的值分类讨论：
（a）当 $m\geqslant 2t+1$ 时，
有 $\begin{aligned} b_{m-2 t+1}+b_{m-2 t+2}+\ldots+b_{i} &=a_{m}+a_{m+1}+\ldots+a_{i+2 t-1} \geqslant i+2 t-m \end{aligned}$ 于是 $b_i$ 是"龙尾"；
（b）当 $t+1\leqslant m\leqslant 2t$ 时，
有 $
b_{1}+b_{2}+\ldots+b_{i} \geqslant a_{m}+a_{m+1}+\ldots+a_{i+2 t-1} \geqslant i+2 t-m \geqslant i
$ 可得 $b_i$ 是"龙尾"；
（c）当 $m\leqslant t$ 时，有 $\begin{aligned} b_{1}+b_{2}+\ldots+b_{i} &=a_{1}+a_{2}+\ldots+a_{i+2t-1}-t \geqslant i+2 t-m-t \geqslant i \end{aligned}$ 同样可得 $b_i$ 也是"龙尾"．
因此，在数列 $b_1 , b_2 , \ldots , b_{n-2t+1}$ 中由归纳假设，有 $\displaystyle \sum\limits_{i=1}^{n-2t+1}b_i \geqslant \left[\frac{n-2t+1}{2}\right]+1$，
故 $\displaystyle
\sum\limits_{i=1}^{n} a_{i}=t+\sum_{i=1}^{n-2 t+1} b_{i} \geqslant t+\left[\frac{n-2 t+1}{2}\right]+1 \geqslant\left[\frac{n}{2}\right]+1
$ 结论对 $n$ 项数列也成立．
综上可知，$\displaystyle \sum\limits_{i=1}^{n}a_i$ 的最小值为 $\left[\dfrac{n}{2}\right]+1$．
答案
解析
备注
