40308 2016 年第 57 屆國際數學奧林匹亞競賽試題解答

終極密碼

遊戲規則：本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數，電腦會提示密碼的所在範圍，玩家必須在6次之內猜到密碼才能過關。

★ 終極密碼為0到100之間 ★
您共有六次機會

作者： 數學奧林匹亞競賽工作小組  　 Download：PDF

2016 年第 57 屆國際數學奧林匹亞競賽試題解答 2016年 9月(159)

2016 年第 57 屆國際數學奧林匹亞競賽 (International Mathematical Olympiad, 簡稱 IMO) 在香港舉行。 本屆共有 109 個國家 (另加 2 個觀察國) 與會、合計 602 位學生 (含 71 位女學生) 代表參賽。 競賽活動是由各國領隊組成的評審會議 (Jury Meeting) 揭開序幕。 除了確認各項議題外, 評審會議的主要工作是挑選本屆的競賽試題。 國際數學奧林匹亞競賽試題是先由各參賽國 (主辦國除外) 於規定時間內提交數道試題, 再由主辦國的試題委員會 (Problem Selection Committee) 研究選出 30 道左右的預選試題, 分屬代數、組合、幾何、 數論等不同領域和不同難度的試題； 最後再經由評審會議票選暨修訂出最後 6 道 IMO 試題, 依主題內容及難易層次分配成兩份試題, 分別在連續的兩天舉行競試, 每天 3 道試題, 考試時間都是 4 小時又 30 分鐘。

本屆試題經由主辦國的試題委員會選出他們認為較適當的試題, 再由各國領隊組成的評審會議經過四天的討論票選出 6 道正式試題, 其中第一題的領域為幾何、 第二題為組合、第三、四題為數論, 第五題為代數, 第六題為組合。 對此次我國代表團所翻譯成正體中文版的 6 道 IMO 試題提供參考解答, 以供國內相關學者、 數學教師等輔導數學資優生之研究、應用與參考。

問題 1：

三角形 $BCF$ 中, $\angle B$ 是直角。 設點 $A$ 在直線 $CF$ 上, 滿足 $FA = FB$、且 $F$ 位於 $A$ 和 $C$ 之間。選取點 $D$ 使得 $DA =DC$、且 $AC$ 是 $\angle DAB$ 的角平分線。再選點 $E$ 使得 $EA = ED$、且 $AD$ 是 $\angle EAC$ 的角平分線。設點 $M$ 為 $CF$ 的中點, 另有一點 $X$ 滿足 $AMXE$ 為平行四邊形 (其中 $AM // EX$、 $AE // MX$)。

證明：直線 $BD$、 $FX$、 $ME$ 三線共點。

試題委員會公布的參考答案：

由題設知 $\angle FBA = \angle FAB = \angle DAC = \angle DCA = \angle EAD = \angle EDA$, 將此共同角記為 $\theta$。由於 $\triangle ABF \sim \triangle ACD$ (等腰三角形, 對應底角相等), 知 $\frac{AB}{AC} = \frac{AF}{AD}$, 於是有 $\triangle ABC \sim \triangle AFD$。由 $EA = ED$, 可得 \begin{equation*} \angle AFD = \angle ABC = 90^\circ + \theta = 180^\circ - \frac{1}{2} \angle AED. \end{equation*} 所以 $F$ 落在以 $E$ 為圓心、以 $EA$ 為半徑的圓上, 也由此有 $EF = EA = ED$。因為 $\angle EFA = \angle EAF = 2 \theta = \angle BFC$, 可得 $E$、 $F$、 $B$ 三點共線。 因為 $\angle EDA = \angle MAD$, 可知 $ED /\!\!/ AM$ (內錯角相等), 故 $E$、 $D$、 $X$ 三點共線。又 $M$ 為 $CF$ 的中點, 且 $\angle CBF = 90^\circ$, 得 $MF = MB$。在等腰三角形 $EFA$ 與 $MFB$ 中, 有 $\angle EFA = \angle MFB$ 以及 $AF = BF$。因此, 這兩個等腰三角形全等, 於是得到 $BM = AE = XM$, 與 $BE = BF + FE = AF + FM = AM = EX$。由此得 $\triangle EMB \simeq \triangle EMX$。由於 $F$ 與 $D$ 這兩點分別落在直 線 $EB$ 及 $EX$ 上, 並且 $EF = ED$, 得知直線 $BD$ 與 $XF$ 對 $EM$ 對稱。 故知此三線共點, 證明完畢。 $\tag*{$\Box$}$

評註： 本題是今年唯一的純幾何題, 難度不高, 作法也有許多種。 圖形中有許多共圓、平行、等腰的條件, 只要能看出來都可得證。 官方另提供一種解法, 把 $BD$、 $FX$、 $ME$ 視為三個圓兩兩的根軸, 於是可由圓冪定理得證。 有興趣的讀者可以試試看。

問題 2：

找出所有的正整數 $n$, 使得我們可以在 $n \times n$ 表格的每一方格中各填入字母 $I$、 $M$、 $O$ 其中之一, 並且符合下列條件：

  • 在任一行及任一列中, 有三分之一的方格填入字母 $I$、三分之一的方格填入 $M$、三分之一的方格填入 $O$；並且
  • 對任一條對角線而言, 如果它的格子數是三的倍數, 則在該對角線中有三分之一的方格填入字母 $I$、三分之一的方格填入 $M$、三分之一的方格填入 $O$。

註： 一個 $n \times n$ 表格的各行各列, 可以按自然順序用 $1$ 至 $n$ 標號。由此, 任一方格可對應到一組正整數 $(i, j)$, 其中 $1 \leqslant i, j \leqslant n$。當 $n \gt 1$ 時, 表格會有 $4n-2$ 條對角線, 分成兩類：第一類對角線係由 $i + j$ 為定值的所有方格 $(i,j)$ 所組成； 而第二類是由 $i - j$ 為定值的所有方格 $(i,j)$ 所組成。

試題委員會公布的參考答案：

$n$ 可以是 $9$ 的任何倍數。

我們首先給一個 $9 \times 9$ 的表格如下：

IIIMMMOOO
MMMOOOIII
OOOIIIMMM
IIIMMMOOO
MMMOOOIII
OOOIIIMMM
IIIMMMOOO
MMMOOOIII
OOOIIIMMM
直接檢查可知上表滿足題設。 當 $n = 9k$, $k$ 為正整數時, 我們可以將上表重複 $k \times k$ 次來得到 $n \times n$ 的表格。 易知所得到的 $n \times n$ 表格的每一行及每一列中, $I$、 $M$、 $O$ 出現的數目都相同。而對長度為 $3$ 的倍數的對角線而言, 該對角線會與如上的任一個 $9 \times 9$ 表格交於長度為 $3$ 的倍數的對角線上 (也可能完全不交)； 由此, 在每一條這樣的對角線上, $I$、 $M$、 $O$ 出現的數目也都相同。至此完成 $(9k) \times (9k)$ 表格的建構。

接下來證明必要性。 因為每一列的格子數必須為 $3$ 的倍數, 所以可設 $n = 3k$, 其中 $k$ 為正整數。 所以我們把 $n \times n$ 的表格分割成 $k \times k$ 個 $3 \times 3$ 的小表格。 我們將每一個小表格的中心格稱為關鍵格； 並稱任一個至少包含一個關鍵格的列、 行、 對角線為關鍵線。 以下計算有序對 $(\ell, c)$ 的數量, 其中 $\ell$ 為關鍵線、 $c$ 為 $\ell$ 上含有字母 $M$ 的方格。將此數量記為 $N$。

首先, 由於每一行、每一列都包含相同數量的 $I$、 $M$、 $O$, 所以每一條關鍵行與每一條關鍵列都包含 $k$ 個 $M$。 接著對任一類的關鍵對角線計數： $M$ 出現的個數是： \begin{equation*} 1 + 2 + \cdots + (k-1) + k + (k-1) + \cdots + 2 + 1 = k^2. \end{equation*} 加總起來, 可知 $N = 4k^2$。

另一方面, 表格中共有 $3k^2$ 個 $M$, 每一個 $M$ 會落在 $1$ 或 $4$ 條關鍵線上。 所以 $N$ 與 $3k^2$ 對模 $3$ 同餘。

由這兩種計數方式, 可知 $4 k^2 \equiv 3 k^2 \pmod{3}$。所以 $k$ 必為 $3$ 的倍數, 亦即 $n$ 必須是 $9$ 的倍數。 證明完畢。 $\tag*{$\Box$}$

評註： 本題為組合中常見的建構問題, 要猜出答案後才能往正確的方向前進。 本題的主要技巧, 其實就是組合學中常見的「數兩次」的方法： 將同一個集合以兩種不同的方法計數, 就能得到滿足題敘情形的必要條件。

問題 3：

設 $P = A_1 A_2 \ldots A_k$ 為平面上的凸多邊形。 頂點 $A_1$、 $A_2$、 $\cdots$、$A_k$ 坐標中的所有數字都是整數, 並且都落在一個圓上。 令 $P$ 的面積為 $S$。給一個正奇數 $n$, 使得 $P$ 的每一條邊之長度平方皆為整數, 並且可被 $n$ 整除。

證明： $2S$ 為整數, 並且可被 $n$ 整除。

試題委員會公布的參考答案：

對所有 $i \geqslant 1$, 令 $A_{k+i} = A_i$。由鞋帶公式 (Shoelace formula)1 1 設三角形頂點分別為 $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$, 則其面積為 $\displaystyle \frac{1}{2} \left| \begin{array}{cccc} x_1 & x_2 & x_3 & x_1 \\ y_1 & y_2 & y_3 & y_1 \end{array} \right|$ 的絕對值；更多邊形亦有類似的公式, 此即為鞋帶公式 Shoelace formula。 , 立知 $2S$ 為正整數。以下我們將利用數學歸納法證明, 在 $k \geqslant 3$ 時, $2S$ 可被 $n$ 整除。 易知我們只需證明 $n$ 是某質數的完全次方的情況, 即 $n = p^t$, 其中 $p$ 為奇質數, $t$ 為正整數。

當 $k = 3$ 時, 設 $P$ 的三邊長分別為 $\sqrt{na}$、 $\sqrt{nb}$、 $\sqrt{nc}$, 其中 $a, b, c$ 為正整數。由海龍公式 (Heron's formula)： \begin{equation*} 16S^2 = n^2 (2ab + 2bc + 2ca - a^2 - b^2 - c^2). \end{equation*} 所以 $16S^2$ 是 $n^2$ 的倍數。因為 $n$ 是奇數, 所以 $2S$ 是 $n$ 的倍數。

現設 $k \geqslant 4$。萬一 $P$ 有某一條對角線的長度平方是 $n$ 的倍數, 則該對角線可將 $P$ 分割成兩個滿足題設的、邊數較少的圓內接多邊形, 由歸納法假設得證。 因此, 我們只需處理任一條對角線的長度平方都不是 $n$ 的倍數的情形。 令 $u_p(r)$ 代表正有理數 $r$ 的質因數分解式中 $p$ 出現的次數。 吾人宣稱下列敘述成立：

引理： 對 $2 \leqslant m \leqslant k-1$, 都有 $up{m} \gt up{m+1}$。

引理證明： 由假設, $up{2} \geqslant t \gt up{3}$, 故 $m = 2$ 的情形成立。

設不等式 $up{2} \gt up{3} \gt \cdots \gt up{m}$ 成立, 其中 $3 \leqslant m \leqslant k-1$。在歸納過程中, 對圓內接四邊形 $A_1 A_{m-1} A_m A_{m+1}$ 使用托勒密 (Ptolemy) 定理： \begin{equation*} A_1 A_{m+1} \times A_{m-1} A_m + A_1 A_{m-1} \times A_m A_{m+1} = A_1 A_m \times A_{m-1} A_{m+1}. \end{equation*} 移項平方可得 \begin{equation} \label{eq:331} \begin{split} A_1 A_{m+1}^2 \times A_{m-1} A_m^2 = &A_1 A_{m-1}^2 \times A_m A_{m+1}^2 + A_1 A_m^2 \times A_{m-1} A_{m+1}^2 \\ &- 2 A_1 A_{m-1} \times A_m A_{m+1} \times A_1 A_m \times A_{m-1} A_{m+1}. \end{split} \end{equation} 由此式知 $2 A_1 A_{m-1} \times A_m A_{m+1} \times A_1 A_m \times A_{m-1} A_{m+1}$ 為整數。我們來考慮 (1) 式每一項中, 質數 $p$ 出現的次數。 由歸納法假設, 有 $up{m-1} \gt up{m}$。而且 $u_p( A_m A_{m+1}^2 ) \geqslant t \gt u_p( A_{m-1} A_{m+1}^2 )$ 亦成立。所以 有 \begin{equation} \label{eq:3-2} u_p( A_1 A_{m-1}^2 \times A_m A_{m+1}^2 ) \gt u_p ( A_1 A_m^2 \times A_{m-1} A_{m+1}^2 ). \end{equation} 接下來, 我們由 (\ref{eq:3-2}) 式可得 \begin{equation*} \begin{split} &\hskip -20ptu_p( 4 A_1 A_{m-1}^2 \times A_m A_{m+1}^2 \times A_1 A_m^2 \times A_{m-1} A_{m+1}^2 ) \\ =\,\, &u_p( A_1 A_{m-1}^2 \times A_m A_{m+1}^2 ) + u_p( A_1 A_m^2 \times A_{m-1} A_{m+1}^2 ) \\ \gt \,\, &2 u_p ( A_1 A_m^2 \times A_{m-1} A_{m+1}^2 ). \end{split} \end{equation*} 由此知 \begin{equation} \label{eq:3-3} u_p( 2A_1 A_{m-1} \times A_m A_{m+1} \times A_1 A_m \times A_{m-1} A_{m+1} ) \gt u_p ( A_1 A_m^2 \times A_{m-1} A_{m+1}^2 ). \end{equation} 綜合 (1)、 (\ref{eq:3-2})、 (\ref{eq:3-3}) 三式, 可知 \begin{equation*} u_p ( A_1 A_{m+1}^2 \times A_{m-1} A_m^2 ) = u_p ( A_1 A_m^2 \times A_{m-1} A_{m+1}^2 ). \end{equation*} 由於 $u_p( A_{m-1} A_m^2 ) \geqslant t \gt u_p( A_{m-1} A_{m+1}^2 )$, 我們得到 $up{m+1} \lt up{m}$。於是引理由數學歸納法得證。$\tag*{$\heartsuit$}$

回到原題。 由引理知 \begin{equation*} t \gt up{3} \gt up{4} \gt \cdots \gt up{k} \geqslant t, \end{equation*} 顯然矛盾！故原命題成立, 即 $2S$ 為 $n$ 的倍數。證明完畢。 $\tag*{$\Box$}$

評註： 此題數論題是本屆最難的試題。 官方解極為巧妙, 利用圓內接四邊形的托勒密定理, 設計出由某點出發的諸條對角線對質因數次數遞降的性質, 從而得到矛盾。 注意到如果對任一奇質數 $p$ 都能證出題敘對 $p^2$ 成立, 那麼整個圖形可以縮小成 $\frac1p$ 倍, 於是可以一路遞降證 畢, 也是極為漂亮的證法。本題另外還可以利用複數系內的高斯整數 (Gaussian integer) 的性質來證明, 其間需要對形如 $4k+1$ 與 $4k+3$ 的質數作不一樣的討論, 是值得接觸過高等數學的人士學習的。

問題 4：

對一個由正整數所組成的集合而言, 如果它至少包含兩個元素, 且每一個元素至少與另一個元素有共同的質因數, 則稱此集合為一個 芳香集。 設 $P(n)=n^2+n+1$。請找出最小的正整數 $b$, 使得我們可以找到非負整數 $a$, 讓集合 \begin{equation*} \{ P(a+1), P(a+2), \dots, P(a+b) \} \end{equation*} 成為一個芳香集。

試題委員會公布的參考答案：

本題 $b$ 的最小可能值為 $6$。

易知對所有的正整數 $n$, $P(n)$ 總是奇數。 先有以下幾個簡單的觀察：

  1. 對任意正整數 $n$, 有 $\bigl( P(n), P(n+1) \bigr) = 1$。 持續利用輾轉相除法, 知 $\bigl( P(n), P(n+1) \bigr) = ( n^2 + n + 1, n^2 + 3n + 3 ) = ( n^2 + n + 1, 2n + 2 ) \\ = ( n^2 + n + 1, n + 1 ) = (1, n+1) = 1$。
  2. 對任意正整數 $n$, 當 $\not\equiv 2 \pmod{7}$ 時, $\bigl( P(n), P(n+2) \bigr) = 1$； 當 $n \equiv 2 \pmod{7}$ 時, $\bigl( P(n), P(n+2) \bigr) = 7$。 證：由於 $(2n+7) P(n) - (2n-1) P(n+2) = 14$ 且 $P(n)$ 總為奇數, 知 $\bigl( P(n), P(n+2) \bigr)$ 必為 $7$ 的因數。直接對 $n \equiv 0, 1, \dots, 6 \pmod{7}$ 逐一檢查即得。
  3. 對任意正整數 $n$, 當 $\not\equiv 1 \pmod{3}$ 時, $\bigl( P(n), P(n+3) \bigr) = 1$； 當 $n \equiv 1 \pmod{3}$ 時, $3 \mid \bigl( P(n), P(n+3) \bigr)$。
    證：由於 $(n+5) P(n) - (n-1) P(n+3) = 18$ 且 $P(n)$ 總為奇數, 知 $\bigl( P(n), P(n+3) \bigr)$ 必為 $9$ 的因數。直接對 $n \equiv 0, 1, 2 \pmod{3}$ 逐一檢查即可。

首先論證 $b \geqslant 6$。由 (i) 立知不存在 $2$ 或 $3$ 個元素的芳香集。 當 $b = 4$ 時, 由條件(i) 知必須 $P(a+1)$ 與 $P(a+3)$ 不互質、 且 $P(a+2)$ 與 $P(a+4)$ 不互質；但根據 (ii) 此兩者不可能同時成立, 故 $b eq 4$。 現在考慮 $P(a+1)$ 到 $P(a+5)$ 等 $5$ 個數字。 由(i)(ii), $P(a+3)$ 必須與 $P(a+1)$、 $P(a+5)$ 其中之一不互質, 由 對稱性可設此數為 $P(a+1)$。 由 (ii) 知 $a \equiv 1 \pmod{7}$, 並得 $\bigl( P(a+2), P(a+4) \bigr) = 1$。 若這五個數字組成芳香集的話, $\bigl( P(a+1), P(a+4) \bigr)$ 與 $\bigl( P(a+2), P(a+5) \bigr)$ 必須同時大於 $1$, 但由 (iii) 此為不可能。 綜上所述, 知 $b \geqslant 6$。

以下建構一個 $6$ 元素的芳香集。由中國剩餘定理, 可取到正整數 $a$ 同時滿足同餘式 \begin{equation*} a+1 \equiv 7 \pmod{19}, \quad a+2 \equiv 2 \pmod{7}, \quad a+3 \equiv 1 \pmod{3}. \end{equation*} 例如, $a = 196$ 同時滿足上列三式。由 (ii), $P(a+2)$ 與 $P(a+4)$ 都是 $7$ 的倍數。由 (iii), $P(a+3)$ 與 $P(a+6)$ 都是 $3$ 的倍數。直接計算知 $19 \mid P(7) = 57$、 $19 \mid P(11) = 133$, 所以 $P(a+1)$ 與 $P(a+5)$ 都是 $19$ 的倍數。所以 $\{ P(a+1), P(a+2), \dots, P(a+6) \}$ 是一個芳香集。證明完畢。 $\tag*{$\Box$}$

評註： 本題是十分直接的數論題, 同學們可以從小的數目 $n$ 出發, 看看 $P(n)$ 有哪些質因數, 觀察其規律性就知道需要證明哪些同餘式了。 在我國現行的課綱中已將相關的數論知識略去, 但這是數學競賽的初等公式, 還是希望有志於此的同學能多加強這些古典的結果。

問題 5：

黑板上寫著方程式 \begin{equation*} (x-1)(x-2)\cdots(x-2016) = (x-1)(x-2)\cdots(x-2016), \end{equation*} 其中等號兩邊各有 $2016$ 個一次因式。請找出最小的正整數 $k$, 使得： 在這 $4032$ 個一次因式中, 我們能夠恰好擦掉 $k$ 個, 讓等號兩邊至少各留下一個一次因式, 且所得到的方程式沒有實數解。

試題委員會公布的參考答案：

$k$ 的最小值為 $2016$。

因為等號兩邊有 $2016$ 個相同的一次因式, 所以我們至少得擦掉 $2016$ 個因式。以下證明：如果我們把等號左邊的一次因式中, 擦掉所有形如 $x-\ell$ ($\ell \equiv 2, 3 \pmod{4}$) 的因式, 同時在等號右邊的一次因式中, 擦掉所有形如 $x-m$ ($m \equiv 0, 1 \pmod{4}$) 的因式；亦即, 考慮下面的方程式： \begin{equation} \label{eq:5-1} \prod_{j=0}^{503} (x-4j-1)(x-4j-4) = \prod_{j=0}^{503} (x-4j-2)(x-4j-3). \end{equation} 我們宣稱 (\ref{eq:5-1}) 式沒有實數解。以下分區討論。

$\bullet$ 第一種情形： $x = 1, 2, \dots, 2016$。

在此情形下, 等號的某一邊等於 $0$ 而另一邊不是 $0$, 所以這些 $x$ 都不是 (\ref{eq:5-1}) 式的解。

$\bullet$ 第二種情形： $4i + 1 \lt x \lt 4i + 2$ 或者 $4i + 3 \lt x \lt 4i + 4$, 其中 $i \in \{ 0, 1, \dots, 503 \}$。

對於 $j \in \{ 0, 1, \dots, 503 \}$ 且 $j eq k$, 乘積 $(x-4j-1)(x-4j-4)$ 為正；而乘積 $(x-4k-1)(x-4k-4)$ 為負。所以等號的左邊小於 $0$。 但是等號右邊的每一組乘積 $(x-4j-2)(x-4j-3)$ ($j \in \{0, 1, \dots, 503\}$) 都為正, 故等號的右邊大於 $0$。因此, 這些範圍的實數 $x$ 都不是 (\ref{eq:5-1}) 的解。

$\bullet$ 第三種情形： $x \lt 1$ 或 $x \gt 2016$, 或者 $4i \lt x \lt 4i+1$, 其中 $i \in \{ 0, 1, \dots, 503 \}$。

將 (\ref{eq:5-1}) 式改寫為： \begin{equation} \label{eq:5-2} 1 = \prod_{j=0}^{503} \frac{ (x-4j-1)(x-4j-4) }{ (x-4j-2)(x-4j-3) } = \prod_{j=0}^{503} \Bigl( 1 - \frac{2}{(x-4j-2)(x-4j-3)} \Bigr). \end{equation} 注意到在這些範圍的實數 $x$, 對所有 $0 \leqslant j \leqslant 503$, 都有 $(x-4j-2)(x-4j-3) \gt 2$。於是 (\ref{eq:5-2}) 式的等號右邊的每一個因子都介於 $0$ 與 $1$ 之間, 乘積必嚴格小於 $1$；但等號的左邊是 $1$。 所以這些範圍的 $x$ 也都不是 (\ref{eq:5-1}) 的解。

$\bullet$ 第四種情形： $4i + 2 \lt x \lt 4i + 3$, 其中 $i \in \{ 0, 1, \dots, 503 \}$。

這次我們將 (\ref{eq:5-1}) 式改寫成 \begin{equation} \label{eq:5-3} \begin{split} 1 &= \frac{x-1}{x-2} \cdot \frac{x-2016}{x-2015} \cdot \prod_{j=1}^{503} \frac{ (x-4j)(x-4j-1) }{ (x-4j+1)(x-4j-2) } \\ &= \frac{x-1}{x-2} \cdot \frac{x-2016}{x-2015} \cdot \prod_{j=1}^{503} \Bigl( 1 + \frac{2}{(x-4j+1)(x-4j-2)} \Bigr). \end{split} \end{equation} 在這些範圍的 $x$, 會使得 $\frac{x-1}{x-2}$ 以及 $\frac{x-2016}{x-2015}$ 大於 $1$, 也會讓連乘積中的每一個括號都大於 $1$, 所以乘起來必定大於 $1$；但等號左邊是 $1$。 所以這些範圍的 $x$ 也都不是 (\ref{eq:5-1}) 式的解。

綜合上面四種情形, 我們已經把所有實數都討論完畢了。 所以 (\ref{eq:5-1}) 式確定沒有實數解, 證明完畢。 $\tag*{$\Box$}$

評註： 本題是困難的代數題。 在領隊會議中, 此題以其多項式的形式而雀屏中選, 而暫時不採用代數領域中的不等式或函數方程的問題。 此題與第 2 題相當, 一樣是得先猜中答案的形式, 才能加以論證； 而證明的過程中又分成幾個分類, 各自以不同程度的手法來論證。 顯示出這道題目的深度。

問題 6：

平面上有 $n \geqslant 2$ 條線段, 其中任兩條線段都交叉, 並且任三條線段不 共點。小杰要對每條線段各選一個端點放一隻青蛙, 並且讓青蛙面對另一個端點。 然後他會拍 $n-1$ 次手；他每拍一次手, 每隻青蛙都馬上向前跳到它所在的線段 上的下一個交點。青蛙永遠不改變它前進的方向。小杰的願望是存在某種擺放青蛙的 方法, 使得任意兩隻青蛙總是不會同時停在同一個交點上。

  1. 證明：如果 $n$ 是奇數, 小杰一定可以實現他的願望。
  2. 證明：如果 $n$ 是偶數, 小杰一定無法實現他的願望。

試題委員會公布的參考答案：

我們畫一個很大的圓將所有線段圍在內部。將每條線段向兩頭延伸成為直線 $\ell_i\, (1\le i\le n)$, 並設直線 $\ell_i$ 交圓於 $A_i$、 $B_i$ 兩點。

(a) 設 $n$ 為奇數。 我們依某方向將圓上的所有交點 $A_i$、 $B_i$ 交錯標上「入」及「出」兩種符號。 由於所有線段的交點都在圓的內部, 對任意的 $1 \leqslant i \leqslant n$, $A_i$ 與 $B_i$ 之間剛好會有$n-1$ 個點。 因為 $n$ 是奇數, 所以 $A_i$、 $B_i$ 這兩點必定其一被標為「入」、而另一被標為「出」。 於是小杰可以將每一個線段上的青蛙擺在比較靠近「入」的端點； 我們宣稱： 這樣的擺法可以達成他的願望, 亦即：對任意的 $i eq j$, $\ell_i$ 與 $\ell_j$ 上的青蛙不會同時到達這兩條線段的交點。

不失一般性, 我們可設 $\ell_i$、 $\ell_j$ 上的青蛙分別由 $A_i$、 $A_j$ 兩點出發。令 $\ell_i$ 與 $\ell_j$ 的交點為 $P$。 由「入」、「出」 點的設計, 我們知道： 在 $A_i$ 與 $A_j$ 之間的圓弧上有奇點個點, 每一個點都屬於某條線段 $\ell_k$。 因為 $\ell_k$ 只會和 $A_iP$ 與 $A_jP$ 這兩條線段的其中之一相交, 所以這裡共產生奇數個交點。 對於其他的任一線段, 與 $A_iP$、 $A_jP$ 兩條線段的交點數必為 $0$ 或 $2$。 所以除了 $P$ 之外, 落在線段 $A_iP$ 及 $A_jP$ 的交點數目必為奇數。 但是, 如果兩隻青蛙同時到達 $P$ 點, 線段 $A_iP$ 與 $A_jP$ 上的交點數目要相等, 故其和為偶數： 此為矛盾。故 (a) 小題得證。

(b) 當 $n$ 為偶數時, 不論小杰如何擺放青蛙, 在 $A_i$、 $B_i$ 中, 我們將背對青蛙前進方向位置的點標為「入」, 另一則標為「出」。 由奇偶性的考慮, 易知圓上會有兩相鄰點同時被標為「入」；不失一般性設此兩點為 $A_i$ 及 $A_j$。 令 $Q$ 為線段 $A_iB_i$ 與 $A_jB_j$ 的交點。 因為 $A_i$、$A_j$ 中間沒有圓與直線的交點, 所以線段 $A_iQ$ 與 $A_jQ$ (除了 $Q$ 之外) 必有相同數目的線段交點, 於是兩條線段上的青蛙就會同時停在 $Q$ 點。 故 (b) 得證。 $\tag*{$\Box$}$

評註： 本題為漂亮的組合題, 由 $n$ 的奇偶性來判別某種特列的配置是否存在。 畫大圓將所有交點圍起來的想法, 曾經在 2015 年的亞太數學奧林匹亞競賽中出現過。 後面的證明其實不會太複雜, 畫幾個小的情形就可猜出一般狀況, 是近年來較為容易的第 6 題。

---本工作小組係由教育部委託國立中央大學, 於「中華民國參加 2016 年亞太數學暨國際數學奧林匹亞競賽計畫」下成立。 本文的主要作者為林延輯助理教授, 任教國立台灣師範大學數學系---

go to Section