IMO 1977 第 2 題探析

2021 年 9 月 1 日
筆記
數學

原題：在一個有限的實數數列中，任意 7 個連續項之和為負數，且任意 11 個連續項之和為正數。求這個數列最多有多少項。

解法一：記這個數列為 a₁, a₂, …, a_k，問題等價於求 k 的最大值，記為 g。假設 g ≥ 7 + 11 – 1 = 17，考察如下的一組序列：

a₁ a₂ … a₁₁

a₂ a₃ … a₁₂

…

a₇ a₈ … a₁₇

這組序列排成一個 7×11 矩陣 A。由題設知，A 的每一行各數之和為正數，所以 A 中各數之和為正數；而 A 的每一列各數之和為負數，所以A 中各數之和為負數，矛盾。這說明 g ≤ 16。

另一方面，可以構造 16 項數列 5, 5, -13, 5, 5, 5, -13, 5, 5, -13, 5, 5, 5, -13, 5, 5 滿足題設要求。所以 g = 16，即這個數列最多有 16 項。

說明1：從國內的資料看到解法一便是當年英國參賽選手 John Rickard 給出的解法。他因為這個巧妙解法還獲得了特別獎。這裡補充一下具體構造滿足題設要求的 16 項數列的一個簡便方法：

令該數列以前 7 項為一個循環段，則其 16 項可記為 a₁, a₂, …, a₇, a₁, a₂, …, a₇, a₁, a₂，這樣可以確保其中任意 7 個連續項之和都相等。

再令該 16 項數列中，任意 7 個連續項之和為 -1，且任意 11 個連續項之和為 1。於是有

a₁ + a₂ + … + a₇ = -1

a₁ + a₂ + a₃ + a₄ = 1 – (-1) = 2

a₂ + a₃ + a₄ + a₅ = 2

a₃ + a₄ + a₅ + a₆ = 2

a₄ + a₅ + a₆ + a₇ = 2

a₅ + a₆ + a₇ + a₁ = 2

a₆ + a₇ + a₁ + a₂ = 2

進一步有 a₅ = a₁, a₆ = a₂, a₇ = a₃, a₁ = a₄, a₆ = a₄，可解出：

a₁ = a₂ = a₄ = 5，a₃ = -13，於是便得到一個滿足題設要求的 16 項數列：

5, 5, -13, 5, 5, 5, -13, 5, 5, -13, 5, 5, 5, -13, 5, 5

在 //math.stackexchange.com/questions/3008035/smallest-size-of-set-of-real-numbers-such-that-the-sum-of-any-seven-is-strictly/ 上看到一個網名為 Dr. Mathva 的人貼出了上述的解法一，以及如下所示的一個通用解法：

解法二：

in the book “The IMO compendium” the authors offer the following solution generalizing the problem

We shall prove a stronger statement: If 7 and 11 in the question are replaced by any positive integers m, n, then the maximum number of terms is m+ n − (m, n) − 1.

Let a₁, a₂, …, a_l be a sequence of real numbers, and let us define s₀ = 0 and s_k = a₁ + … + a_k (k = 1, …, l). The given conditions are equivalent to s_k > s_k+m for 0 ≤ k ≤ l − m and s_k < s_k+n for 0 ≤ k ≤ l − n.

Let d = (m, n) and m = m’d, n = n’d. Suppose that there exists a sequence (a_k) of length greater than or equal to l = m+ n − d satisfying the required conditions. Then the m’ + n’ numbers s₀, s_d, . . . , s_{(m’+n’−1)d} satisfy n’ inequalities s_k+m < s_k and m’ inequalities s_k < s_k+n. Moreover, each term s_kd appears twice in these inequalities: once on the left-hand and once on the right-hand side. It follows that there exists a ring of inequalities s_i1 < s_i2 < … < s_ik < s_i1 , giving a contradiction.

On the other hand, suppose that such a ring of inequalities can be made also for l = m + n − d − 1, say s_i1 < s_i2 < … < s_ik < s_i1. If there are p inequalities of the form a_k+m < a_k and q inequalities of the form a_k+n > a_k in the ring, then qn = rm, which implies m’ | q, n’ | p and thus k = p + q ≥ m’ + n’. But since all i₁, i₂, … , i_k are congruent modulo d, we have k ≤ m’ + n’ − 1, a contradiction. Hence there exists a sequence of length m + n − d − 1 with the required property.

而按照 Dr. Mathva 的說法，這個解法二才是 John Rickard 的解法——This second solution was offered in the IMO by John Rickard, from the UK, who received a special price for such an original approach.

具體看一下這個通用解法。用正整數 m 和 n 替換原題中的 7 和 11，若 m = n，按通用解法給出的通用最大項數為 g = m + n – (m,n) – 1 = m – 1【為清晰起見，這裡用字母 g 取代通用解法里使用的 l】，即總項數為 m – 1，這時任意 m – 1個實數構成的數列都認為是滿足題設要求的，但實際情形是根本不存在題設所言的實數數列滿足任意連續 m 項之和同時為正數和負數，在這樣的前提下談論這個數列最大項數是沒有意義的。

其它的情形，不妨令 m < n，若 m | n，按通用解法給出的通用最大項數為 g = m + n – (m,n) – 1 = n – 1，這時任意 n – 1個負實數構成的數列都認為是滿足題設要求的，但實際情形是根本不存在題設所言的實數數列滿足任意連續 m 項之和為負數且任意連續 n 項之和為正數，在這樣的前提下談論這個數列最大項數也是沒有意義的。

以下就 m < n 且 m ≠ (m,n) 的情形對上述通用解法進行分析。

第二段引入 s_k = a₁ + a₂ + … + a_k, (1 ≤ k ≤ g) 和 s₀ = 0，並由題設得到

s_k > s_k+m, (0 ≤ k ≤ g – m)

s_k < s_k+n, (0 ≤ k ≤ g – n)

都是很好懂的。但第三段的內容則顯得比較晦澀。以下取 m = 6 且 n = 10 為例具體看一下這一段：

Let d = (m, n) and m = m’d, n = n’d.

即 d = (m, n) = (6, 10) = 2，m’ = 3，n’ = 5；此時 m’ + n’ – 1 = 7

Suppose that there exists a sequence (a_k) of length greater than or equal to g = m+ n − d satisfying the required conditions. Then the m’ + n’ numbers s₀, s_d, . . . , s_{(m’+n’−1)d} satisfy n’ inequalities s_k+m < s_k and m’ inequalities s_k < s_k+n.

這一句是說，假設數列 a₁, a₂, …, a_h，h ≥ g = m + n – d = 14，滿足題設要求，那麼 s₀, s₂, s₄, . . . , s₁₄ 這 8 個數會滿足以下兩組不等式（左側一組 5 個，右側一組 3 個，共 8 個不等式）：

s₆ < s₀ s₀ < s₁₀

s₈ < s₂ s₂ < s₁₂

s₁₀ < s₄ s₄ < s₁₄

s₁₂ < s₆

s₁₄ < s₈

Moreover, each term s_kd appears twice in these inequalities: once on the left-hand and once on the right-hand side. It follows that there exists a ring of inequalities s_i1 < s_i2 < · · · < s_ik < s_i1 , giving a contradiction.

這兩句是說，s₀, s₂, s₄, . . . , s₁₄ 這 8 個數中的每個數都在 8 個 x < y 型的不等式中的左端和右端各出現一次，於是可推出這 8 個數中一定存在 s_i1 < s_i2 < · · · < s_ik < s_i1 這樣的環路關係，導致一個數小於它自身的矛盾。這是因為，按假設的條件，每個數都不是最大的（也不是最小的）。

至此，第三段的邏輯已經很清楚了。接着看第四段：

On the other hand, suppose that such a ring of inequalities can be made also for g = m + n − d − 1, say s_i1 < s_i2 < · · · < s_ik < s_i1. If there are p inequalities of the form a_k+m < a_k and q inequalities of the form a_k+n > a_k in the ring, then qn = rm, which implies m’ | q, n’ | p and thus k = p + q ≥ m’ + n’.

這幾句（如標紅部分所示，這裡有幾處筆誤，a 應該是 s，r 應該是 p）是說，假設 g = m + n – d – 1 的情形也會出現 s_i1 < s_i2 < · · · < s_ik < s_i1 這樣的環路關係，這個環路中有 k 個 x < y 型不等式。若這 k 個不等式中，p 個來自 s_k+m < s_k，q 個來自 s_k < s_k+n，則有 qn = pm，由此有 m’ | q 和 n’ | p，因此 k = p + q ≥ m’ + n’。

解釋一下 qn = pm 的由來：環路中有 k 個 x < y 型不等式，從 i₁ 開始，做了 p 次減 m 操作和 q 次加 n 操作後又回到了 i₁，即有 i₁ – pm + qn = i₁，於是有 qn = pm。隨後的結論很直觀了。

But since all i₁, i₂, . . . , i_k are congruent modulo d, we have k ≤ m’ + n’ − 1, a contradiction. Hence there exists a sequence of length m + n − d − 1 with the required property.

這兩句是說，由 i₁ ≡ i₂ ≡ … ≡ i_k (mod d)，就有 k ≤ m’ + n’ − 1，這與 k ≥ m’ + n’ 構成衝突。因而，滿足題設要求的長度為 m + n − d − 1 的數列是存在的。

i₁, i₂, . . . , i_k 模 d 同餘是顯然的，因為從 i₁ 到 i_k 的逐次變換都是減 m 或加 n，而 d = (m,n)。又因為 i₁, i₂, . . . , i_k 取值都是 [0, m + n – d -1] 範圍內的整數，兩兩不同且模 d 同餘，而在 0, 1, …, m + n – d -1 這 m + n – d 個整數中模 d 同餘的數最多為 (m + n – d) / d = m’ + n’ − 1 個，即有 k ≤ m’ + n’ − 1。與 k ≥ m’ + n’ 矛盾，這說明當 g = m + n − d − 1 時，s₀, s₁, …, s_g 中不存在 x < y 型環。於是就認定存在數列 a₀, a₁, …, a_g 滿足題設要求。這是通用解法中最為奇特的部分了，即免除了構造一個具體的滿足題設要求的數列的環節。

這裡不做由 s₀, s₁, …, s_g 中不存在 x < y 型環，到存在數列 a₀, a₁, …, a_g 滿足題設要求的嚴格證明。僅以 m = 6 和 n = 10 為例，來實際構造一個滿足題設要求的數列 a₀, a₁, …, a_g 實例：

這時，g = m + n – d – 1 = 13，出自 s_k+m < s_k 的全體不等式（共計有 m + n – d – 1 – m + 1 = n – d = 8 個）為：

s₆ < s₀，s₇ < s₁，s₈ < s₂，s₉ < s₃，s₁₀ < s₄，s₁₁ < s₅，s₁₂ < s₆，s₁₃ < s₇

出自 s_k < s_k+n 的全體不等式（共計有 m + n – d – 1 – n + 1 = m – d = 4 個）為：

s₀ < s₁₀，s₁ < s₁₁，s₂ < s₁₂，s₃ < s₁₃

據此試圖排出 s₀, s₁, …, s₁₃ 從小到大的順序，得到：

s₈ < s₂ < s₁₂ < s₆ < s₀ < s₁₀ < s₄

s₉ < s₃ < s₁₃ < s₇ < s₁ < s₁₁ < s₅

s₀ = 0，不妨令 s₆ = -1，s₁₀ = 1，s₁₂ = -2，s₄ = 2，s₂ = -3，s₈ = -4

同樣，不妨令 s₁ = 0，s₇ = -1，s₁₁ = 1，s₁₃ = -2，s₅ = 2，s₃ = -3，s₉ = -4

由 a_i = s_i – s_i-1，可得

(a₁, a₂, …, a₁₃) = (0, -3, 0, 5, 0, -3, 0, -3, 0, 5, 0, -3, 0)

這便是 m = 6, n = 10 時，滿足題設要求的最大項數為 13 的一個數列實例。

由上面的分析過程可知，原題擴展到一般情形後還可以進一步限定是整數數列，其結論依然成立。

說明2：上面的解法一和解法二存在一定的關聯性。回顧解法一里那個 7×11 矩陣

a₁ a₂ … a₁₁

a₂ a₃ … a₁₂

…

a₇ a₈ … a₁₇

對矩陣的第 i 行求和，得到：

s_i+10 – s_i-1 > 0, i = 1,2,…,7

對矩陣的第 j 列求和，得到：

s_j+6 – s_j-1 < 0, j = 1,2,…,11

矩陣的各行求和相加，記為 s_r，得到：

s_r = (s₁₁ + s₁₂ + … +s₁₇) – (s₀ + s₁ + … + s₆) > 0

矩陣的各列求和相加，記為 s_c，得到：

s_c = (s₇ + s₁₂ + … +s₁₇) – (s₀ + s₁ + … + s₁₁) < 0

由 (s₀ + s₁ + … + s₆) + (s₇ + s₁₂ + … +s₁₇) = (s₀ + s₁ + … + s₁₁) + (s₁₁ + s₁₂ + … +s₁₇)

可知，s_r = s_c，這樣就連通到了解法一的思路。但是解法一里的矩陣表示法確實是非常直觀的，這種直觀性明顯優於解法二。

我們甚至可以說，對於證明一般情形下的必要性結論，即 g ≤ m + n – (m, n) – 1，解法一在直觀性上也是優於解法二的。以上面分析解法二引入的 m = 6, n = 10 的特殊情形來具體看一下用解法一的思路如何求解：

拓展題：在一個有限的整數數列中，任意 6 個連續項之和為負數，且任意 10 個連續項之和為正數。求這個數列最多有多少項。

分析：若直接套用前述的解法一，給出如下的矩陣：

a₁ a₂ … a₁₀

a₂ a₃ … a₁₁

…

a₆ a₇ … a₁₅

只能得到 g ≤ 6 + 10 – 1 – 1 = 14，若接着試圖去構造一個滿足題設要求的 a₁, a₂, …, a₁₄ 數列實例就會碰壁了。事實上，前述的解法一之所以對原題起作用是因為 (m, n) = (7, 11) = 1。因此拓展題需要對前述的解法一加以改進，即要把 (m, n) 考慮進去。

由於d = (m, n) = (6, 10) = 2，把數列 a₁, a₂, …, a_2k 的項從左至右兩個一組結對求和，可得到一個新數列 b₁, b₂, …, b_k，其中 b_i = a_2i-1 + a_2i, i=1,2,…,k

若數列 a₁, a₂, …, a_2k 中任意連續 m = 6 項之和為負數，且任意連續 n = 10 項之和為正數，則在數列 b₁, b₂, …, b_k 滿足：任意連續 m/d = 3 項之和為負數，且任意連續 n/d = 5 項之和為正數。考察如下的 3×5 矩陣 B

b₁ b₂ … b₅

b₂ b₃ … b₆

b₃ b₄ … b₇

對每行求和，可得 B 中各數之和為正數；而對每列求和，可得 B 中各數之和為負數，矛盾。因此為使得數列 a₁, a₂, …, a_2k 滿足題設要求，k 必須小於等於 m/d + n/d – 1 = 7，於是有 g ≤ d(m/d + n/d – 1) – 1 = m + n – d – 1 = 13。再用前面說明1 里的方法很容易實際構造出滿足題設要求的項數為 13 的數列實例：

(a₁, a₂, …, a₁₃) = (0, -3, 0, 5, 0, -3, 0, -3, 0, 5, 0, -3, 0)

因此 g = 13。

說明3：對於一般情形的結論，即正整數 m 和 n 滿足 m < n 且 m ≠ (m, n) 時，滿足任意 m 項之和為負數，且任意 n 項之和為正數的整數隊列 a1, a2, …, ak 的最大項數為 g = m + n – (m, n) – 1。由上面的改進的解法一可以很直觀地推導出 g ≤ m + n – (m, n) – 1 這個必要性的結論，但是進一步通過構造可行數列來證明 g = m + n – (m, n) – 1 就非常困難了。對比之下，解法二的做法是極其巧妙和高明的，它不是通過構造可行實例來證明結論，而是證明項數為 g = m + n – (m, n) – 1 的可行實例一定存在。

當給定 m 和 n 具體的取值時，如前面分析所示，用解法一和解法二都可以很容易地構造出具體的滿足題設要求的數列實例。但就一般情形而言，構造一個項數為 g = m + n – (m, n) – 1 的滿足題設要求的通用數列實例應該是非常困難的（甚至是不可能的）。

附言：

為搞清楚當年 John Rickard 提供的解答到底是解法一還是解法二，在網上又進一步查了一些資料。

在 //artofproblemsolving.com/community/c6h61033p369641 上看到 enescu 貼出的當年捷克選手 Martin Čadek 的一個解法：

Let $x_1,x_2,\ldots$ be the given sequence and let $s_n=x_1+x_2+\ldots+x_n$ .
The conditions from the hypothesis can be now written as $s_{n+7}<s_n$ and $s_{n+11}>s_n$ for all $n\ge 1$ .
We then have:
$0<s_{11}<s_4<s_{15}<s_8<s_1<s_{12}<s_5<s_{16}<s_9<s_2<s_{13}<s_6<s_{17}<s_{10}<s_3<s_{14}<s_7<0,$
a contradiction. Therefore, the sequence cannot have $17$ terms.
In order to show that $16$ is the answer, just take 16 real numbers satisfying
$s_{10}<s_3<s_{14}<s_7<0<s_{11}<s_4<s_{15}<s_8<s_1<s_{12}<s_5<s_{16}<s_9<s_2<s_{13}<s_6$ .
We have $x_1=s_1$ and $x_n=s_n-s_{n-1}$ for $n\ge 2$ . Thus we found all sequences with the given properties.

不難看出，這是前述解法二針對 m = 7, n = 11 的表述，應對原題是沒有問題的，Martin Čadek 也確實因為這個解法得到了特別獎（詳見 //www.imo-official.org/team_r.aspx?code=CZS&year=1977）

另外，pbornsztein 指出：

More generally, it can be shown that :
If $p,q$ are any two distinct positive integers such that none of them divides the other, and if a sequence has the property that the sum of any $p$ consecutive terms is always positive and the sum of any $q$ consecutive terms is negative then the maximal length of this sequence is $p+q-d-1$ where $d = \gcd (p,q).$