连续和的矛盾

Consecutive sums

专题: Discrete Math / 离散数学
难度: L6
来源: Brainstellar

题目详情

有一个实数序列。乐观者说：“任意连续 8 项之和为正。”悲观者说：“任意连续 5 项之和为负。”

两人能同时正确吗？若能，这个序列的长度最多是多少？

提示：把连续和写成若干行并做总和比较。

An optimist and a pessimist are examining a sequence of real numbers. The optimist remarks, ‘Oh jolly! The sum of any eight consecutive terms is positive!’ But the pessimist interjects, ‘Not so fast, the sum of any five consecutive terms is negative.’ Can they both be right? Atmost how large can this sequence be?

Hint

One easy proof is to construct rows, starting from ai, and satisfying one of the sum properties - optimist or pessimist. The column sum can follow the other property. Try making a contradiction.

解析

最多长度为 11。

若长度为 12，则可以写出 8 个“连续 5 项和为负”的不等式（从 $a_1+\cdots+a_5$ 到 $a_8+\cdots+a_{12}$ ）。把这些不等式按列相加，相当于把每个 $a_i$ 加了若干次。

另一方面，“任意连续 8 项和为正”也会对同样的总加权和给出正的下界，产生矛盾。

因此长度不能达到 12，故最大为 11（并且可构造例子）。

Original Explanation

Solution

Suppose such a sequence with terms {ai} has length 12

a1+a2+...+a5<0 a2+a3+...+a6<0 .. a8+a9+...+a12<0

Note that rows sums are negative and column sums are positive. This is contradiction to the total sum! So max length of sequence is 11. This sequence can be constructed but we wont cover the instruction. Example: 1 at positions 1,3,4,6,8,9,11 and -1.6 at positions 2,5,7,10.