| 發刊日期 |
2017年9月
|
|---|---|
| 標題 | 2017 年第58 屆國際數學奧林匹亞競賽試題解答 |
| 作者 | |
| 關鍵字 | |
| 檔案下載 | |
| 全文 |
2017 年第 58 屆國際數學奧林匹亞競賽 (International Mathematical Olympiad, 簡稱 IMO) 在巴西舉行。本屆共有 111 個國家 (另加 1 個觀察國) 與會、 合計 615 位學生 (含 62 位女學生) 代表參賽。 競賽活動是由各國領隊組成的評審會議 (Jury Meeting) 揭開序幕。 除了確認各項議題外, 評審會議的主要工作是挑選本屆的競賽試題。 國際數學奧林匹亞競賽試題是先由各參賽國 (主辦國除外) 於規定時間內提交數道試題, 再由主辦國的試題委員會 (Problem Selection Committee) 研究選出 30 道左右的預選試題, 分屬代數、 組合、幾何、數論等不同領域和不同難度的試題; 最後再經由評審會議票選暨修訂出最後 6 道 IMO 試題, 依主題內容及難易層次分配成兩份試題, 分別在連續的兩天舉行競試, 每天 3 道試題, 考試時間都是 4 小時又 30 分鐘。 本屆試題經由主辦國的試題委員會選出他們認為較適當的試題, 再由各國領隊組成的評審會議經過四天的討論票選出 6 道正式試題, 其中第一題的領域為數論, 第二題為代數, 第三題為組合, 第四題為幾何, 第五題為組合, 第六題為數論。 對此次我國代表團所翻譯成正體中文版的 6 道 IMO 試題提供參考解答, 以供國內相關學者、數學教師等輔導數學資優生之研究、應用與參考。 問題 1： 對於每個整數 $a_0 \gt 1$, 用以下方法定義數列 $a_0$, $a_1$, $a_2$, $\ldots$ ： $$ a_{n+1} =\left\{\begin{array}{lcl} \sqrt{a_n}&\quad~ & \mbox{若}\sqrt{a_n}\mbox{為整數} \\ a_n + 3 && \mbox{其他情況} \end{array} \right. \quad \mbox{對於所有}\ n \geqslant 0 \mbox{皆成立} $$ 試求所有可能值 $a_0$, 滿足存在一個數 $A$, 使得有無窮多個 $n$ 讓 $a_n=A$。 試題委員會公布的參考答案： 滿足題意的 $a_0$ 為所有 $3$ 的倍數。 基於 $a_{n+1}$ 的值被 $a_n$ 唯一確定, 因此若存在 $n \neq m$ 使得 $a_n=a_m$, 則此數列將在某充分大的項數後為週期數列。 因此, 我們只需求所有會讓數列會進入週期的 $a_0$ 即可。 以下先證明四個性質：
綜以上, 我們知 $a_0 \equiv 0 (\mbox{mod }3)$ 滿足題意, 而若 $a_0 \not\equiv 0 (\mbox{mod }3)$ 則數列終將遞增。$\Box$ 評註： 本題是簡單的數論題, 僅需簡單的同餘與最小性討論, 適合作為習題。 問題 2： 令 $\mathbb{R}$ 表示所有實數所成的集合。 試求所有函數 $f \colon \mathbb{R} \to \mathbb{R}$ 滿足對於所有實數 $x$ 和 $y$ $$ f \left( f(x) f(y) \right) + f(x+y) = f(xy) $$ 皆成立。 試題委員會公布的參考答案： 滿足題意的所有函數為 $f(x)=0$, $f(x)=x-1$ 與 $f(x)=1-x$。 以上代回驗證可知確為其解。以下證明這些是所有的解。 首先, 易見若 $f(x)$ 為一解, 則 $-f(x)$ 亦為一解, 故以下不失一般性假設 $f(0) \leq 0$。 因此以下將證明 $f(x)=0$ 或 $f(x)=x-1$。 其次, 對於任何 $x \neq 1$, 取 $y$ 使得 $x+y=xy \Leftrightarrow y = \frac{x}{x-1}$, 帶回題式得 \begin{equation}\label{P2-1} f\left( f(x) f\left( \frac{x}{x-1}\right)\right)=0 \end{equation} 對於所有 $x \neq 1$ 都成立。 進一步取 $x=0$ 帶入 (\ref{P2-1}), 我們有 \begin{equation}\label{P2-2} f\left( f(0)^2 \right) = 0. \end{equation} 因此 $f(x)$ 至少有一零點 $f(0)^2$。 以下分兩種狀況討論 (注意到不失一般性假設 $f(0) \leq 0$)：
評註： 本函數方程在大會評為中高難度, 但尚屬傳統題型, 關鍵在單射的證明手法上較為特殊。 本題台灣隊相對於各國而言成績較佳, 顯見台灣在代數訓練上仍屬扎實。 問題 3： 一位獵人和一隻隱形的兔子在歐氏平面上玩一場遊戲。 兔子的起點 $A_0$ 和獵人的起點 $B_0$ 為同一點。 在遊戲的 $n-1$ 回合後, 兔子所在的位置為 $A_{n-1}$, 獵人所在的位置為 $B_{n-1}$。 在遊戲的第 $n$ 回合, 以下三件事情會依序發生。
試題委員會公布的參考答案： 獵人沒有這樣的策略。 兔子「獲勝」。 如果答案是肯定的, 那獵人必須有個不論兔子怎麼跑或裝置怎麼回報都能成立的策略。 我們將證明反面的命題： 在最不幸的狀況下, 獵人無論如何都無法保證在 $10^9$ 個回合後她和兔子的距離可以在 $100$ 內。 令 $d_n$ 為第 $n$ 回合結束時獵人與兔子之間的距離。 顯然若存在 $n \lt 10^9$ 使得 $d_n\gt 100$, 則兔子已自動獲勝： 牠只要每回合都以遠離獵人的方向直線跑出去, 獵人與兔子之間的距離便保持在 $100$ 以上。 以下證明, 當 $d_n\lt 100$ 時, 兔子總有個跑法, 使得在裝置的幫助下, 無論獵人怎麼應對, 兔子每 $200$ 回合都有機會讓 $d_n^2$ 增加 $\dfrac{1}{2}$。 如此一來, $d_n^2$ 將在 $2 \times 10^4 \times 200 = 4 \times 10^6 \lt 10^9$ 內便達到 $10^4$, 故兔子獲勝。 假設第 $n$ 回合時, 獵人在 $H_n$, 兔子在 $R_n$, 且我們進一步讓兔子在此時暫時對獵人現身 (因此獵人可以忘掉之前裝置提供的所有資訊。) 令 $r = \overleftrightarrow{H_n R_n}$, 並不失一般性假設其為水平線。 令 $Y_1$ 和 $Y_2$ 為 $r$ 上方與下方和兔子距離 $200$, 和 $r$ 距離 $1$, 且遠離獵人的兩點, 如圖 1。
兔子的策略很單純： 從 $Y_1$ 與 $Y_2$ 中挑一點, 然後花 $200$ 回合筆直往其前進。 注意到在這 $200$ 回合間, 兔子跟 $r$ 的距離始終保持在 $1$ 以內, 因此我們可以讓裝置回報的點 $\{ P_m: n+1 \leq m \leq n+200 \}$ 都落在 $r$ 上。 如此一來, 獵人完全無法得知兔子是選擇 $Y_1$ 或 $Y_2$。 現在, 給定獵人看見 $\{ P_m: n+1 \leq m \leq n+200 \}$, 他要怎麼應對?
因此我們只需要估計 $y^2$。 令 $Z$ 為 $Y_1Y_2$ 中點, $R'$ 為 $r$ 上與 $R_n$ 相距 $200$ 且在 $Z$ 右側的點, 並令 $\epsilon = ZR'$ ( 注意到 $H'R'=d_n$。) 則 \begin{equation*} y^2 = 1 + (H'Z)^2 = 1+(d_n-\epsilon)^2 \end{equation*} 其中 \begin{equation*} \epsilon = 200 - R_nZ = 200 - \sqrt{200^2-1} = \frac{1}{200 + \sqrt{200^2-1}} \gt \frac{1}{400}. \end{equation*} 又 $\epsilon^2+1=400\epsilon$, 因此 \begin{equation*} y^2 = d_n^2 - 2\epsilon d_n + \epsilon^2+1 = d_n^2 + \epsilon(400-2d_n). \end{equation*} 基於 $\epsilon \gt \dfrac{1}{400}$ 且我們假設 $d_n \lt 100$, 我們有 $y^2 \gt d_n^2 + \dfrac{1}{2}$。 故我們證明兔子有機會讓 $d_{n+200}^2 \gt d_n^2 + \dfrac{1}{2}$。 兔子獲勝！ $\Box$ 評註： 這是本屆最創新也是最難的題目, 全部 $600$ 餘位考生中僅有兩位全對, 另兩位獲得 $4$ 分以上成績, 平均分為 $0.042$ 分。 本題的出現是否代表數學奧林匹亞的一個新的未來潮流, 值得關注。 問題 4： 令 $R$ 和 $S$ 為圓 $\Omega$ 上相異兩點使得 $RS$ 不是直徑。 令 $\ell$ 為 $\Omega$ 在 $R$ 的切線。 平面上一點 $T$ 使得 $S$ 為 $RT$ 線段的中點。 點 $J$ 在圓 $\Omega$ 的劣弧 $RS$ 上, 使得三角形 $JST$ 的外接圓 $\Gamma$ 和 $\ell$相交於兩相異點。 令 $A$ 為 $\Gamma$ 與 $\ell$ 的交點中較接近 $R$ 者。 直線 $AJ$ 與 $\Omega$ 交於另一點 $K$。 試證 $KT$ 與 $\Gamma$ 相切。 試題委員會公布的參考答案： 透過圓 $\Omega$ 與 $\Gamma$, 我們有 $\angle KRS = \angle KJS = \angle ATS$。 另一方面, 由於 $RA$ 是 $\Omega$ 的切線, 我們有 $\angle SKR = \angle SRA$。 因此 $\Delta ART$ 與 $\Delta SKR$ 相似, 且 \begin{equation*} \frac{RT}{RK} = \frac{AT}{SR} = \frac{AT}{ST}. \end{equation*} 末式結合 $\angle ATS = \angle KRT$, 我們得到 $\Delta AST$ 相似於 $\Delta TKR$, 故 $\angle SAT = \angle RTK$。 故 $KT$ 切 $\Gamma$ 於 $T$, 證畢。$\Box$ 評註： 本題為簡單幾何問題, 解法眾多, 適合做為練習題。 本屆沒有中等或困難的幾何問題, 實屬遺憾。 問題 5： 給定整數 $N \geqslant 2$。 有 $N(N+1)$ 位身高兩兩不同的足球員以某種順序排成一列。 教練想要從這列中移除 $N(N-1)$ 個人, 使得剩下 $2N$ 個人所形成的一列, 滿足以下 $N$ 個條件：
試題委員會公布的參考答案： 將隊伍拆成 $N$ 段, 每區 $N+1$ 個人。 我們將證明可以從每區移除 $N-1$ 個人來達成題目的目標。 首先, 建構一個 $(N+1)\times N$ 的矩陣, 其中 $x_{i,j}$ 是第 $j$ 段裡第 $i$ 高的人的身高; 換言之, 矩陣的每一直列是每一段的人的身高, 由高到矮, 從上而下依序排列。 我們將把此矩陣的直列交換。 首先, 透過列交換, 我們可以讓 $x_{2,1} = \max \{ x_{2,i}: i = 1, 2$, $\ldots, N \}$ (也就是把第二橫排最大的數換到第一直列。) 固定第一直排後, 交換後面的 $N-1$ 直列讓 $x_{3,2} = \max \left\{ x_{3,i}: i = 2, 3,\ldots, N \right\}$ (也就是把第三橫排最大的數換到第二直列。) 依此類推, 讓 $x_{k+1,k} = \max \left\{ x_{k+1,i}: i = k, k+1,\ldots, N \right\}$, 最終得到如下的矩陣： $$ \begin{matrix} {\bf x_{1,1}} & & x_{1,2} & & x_{1,3} & \cdots & x_{1,N-1} & & x_{1,N} \\ {\bf \vee} & & \vee & & \vee & & \vee & & \vee \\ {\bf x_{2,1}} & {\bf \gt } & {\bf x_{2,2}} & & x_{2,3} & \cdots & x_{2,N-1} & & x_{2,N} \\ \vee & & {\bf \vee} & & \vee & & \vee & & \vee \\ x_{3,1} & & {\bf x_{3,2}} & {\bf \gt } & {\bf x_{3,3}} & \cdots & x_{3,N-1} & & x_{3,N} \\ \vee & & \vee & & {\bf \vee} & & \vee & & \vee \\ \vdots & & \vdots & & \vdots & \ddots & \vdots & & \vdots \\ \vee & & \vee & & \vee & & {\bf \vee} & & \vee \\ x_{N,1} & & x_{N,2} & & x_{N,3} & \cdots & {\bf x_{N,N-1}} & \gt & x_{N,N} \\ \vee & & \vee & & \vee & & {\bf \vee} & & \vee \\ x_{N+1,1} & & x_{N+1,2} & & x_{N+1,3} & \cdots & {\bf x_{N+1,N-1}} & {\bf \gt } & {\bf x_{N+1,N}} \end{matrix} $$ 至此, 我們可以大膽將除了以下身高外的人都移除： \begin{equation*} x_{1,1} \gt x_{2,1} \gt x_{2,2} \gt x_{3,2} \gt \cdots \gt x_{N, N-1} \gt x_{N,N} \gt x_{N+1,N}. \end{equation*} 注意到由於前面的分段, $x_{k,k}$與$x_{k+1,k}$必然會是相鄰的兩個人, 從而此法留下的$2N$個人滿足題意。證畢。$\Box$ 評註： 這是一題乍看簡單但異常困難的組合, 正確的道路非常狹窄, 容易從一開始就走上數學歸納法的死胡同, 然後發現你無法同時控制高度與位置兩個資訊。 令人想起 $2011$ 荷蘭 IMO 的風車題。 問題 6： 一個有序整數對 $(x,y)$ 被稱為互質格點 若 $x$ 和 $y$ 的最大公因數為 $1$。 給定一個由互質格點所組成的有限集 $S$, 證明存在一個正整數 $n$ 以及整數 $a_0$, $a_1$, $\dots$, $a_n$, 使得對於所有在 $S$ 中的 $(x,y)$, 我們都有： $$ a_0 x^n + a_1 x^{n-1} y + a_2 x^{n-2} y^2 + \cdots + a_{n-1} x y^{n-1} + a_n y^n = 1. $$ 試題委員會公布的參考答案： 首先, 注意到若我們能找到 $f(x,y)=\pm 1$, 則我們取 $f(x,y)^2=1$ 即可。 將 $S$ 中的互質格點編號為 $(x_1,y_1)$ 至 $(x_n, y_n)$。 注意到若 $(x_i,y_i)$ 與 $(x_j,y_j)$ 若在過原點的同一條直線上, 則必有 $(x_i,y_i) = (-x_j, -y_j)$; 而基於 $f$ 是齊次的, 必有 $f(x_i,y_i)=\pm f(x_j,y_j)$。 因此我們可以假設 $S$ 中的任兩點與原點三點不共線。 考慮齊次多項式 $l_i(x,y) = y_ix - x_iy$, 並定義 \begin{equation*} g_i(x,y) = \prod_{j \neq i} l_j(x,y). \end{equation*} 注意到 $l_i(x_j, y_j)=0$ 若且唯若 $j=i$ (因三點不共線), 因此對於所有 $j \neq i$, $g_i(x_j,y_j)=0$。 定義 $a_i = g_i(x_i, y_i)$, 並注意到 $a_i \neq 0$。 總結來說, $g_i(x,y)$ 是個 $n-1$ 次多項式, 且有以下性質：
透過以上性質, 對於所有 $N \geq n-1$, 我們都可以取到一個 $N$ 次齊次多項式滿足以上性質; 更精確地說, 若令 $I_i(x,y)$ 為一次齊次多項式滿足 $I_i(x_i,y_i)=1$ (存在性因 $(x_i, y_i)$ 為互質格點而保證), 則 $I_i(x,y)^{N-(n-1)}g_i(x,y)$ 滿足上述性質。 現在, 我們可以將原題簡化為證明以下命題： 命題一： 對於所有正整數 $a$, 存在次數至少 $1$ 的整係數齊次多項式 $f_a(x,y)$, 使得 $f_a(x,y) \equiv 1 (\mbox{mod } a)$ 對所有互質數對 $(x,y)$ 皆成立。 要看出為什麼命題一可以推得原題, 取 $a$ 為所有 $a_i$ 的最小公倍數, 並依照命題一取 $f_a$。 取充分大的 $k$ 讓 $f_a(x,y)^k$ 的次數至少為 $n-1$, 再扣除 $g_i$ 的適當乘積即可。 故我們僅需證明命題一即可。 首先, 若 $a$ 是某質數的冪次 $p^k$, 則
現在假設 $a = q_1 q_2 \cdots q_k$, 其中每個 $q_i$ 都是質數的冪次且兩兩互質。 令 $ f_{q_i}$ 為命題一所得函數, 並令 $F_{q_i}$ 為 $f_{q_i}$ 的若干冪次使得它們都是同樣的次數。 注意到 \begin{equation*} \frac{a}{q_i}F_{q_i}(x,y) \equiv \frac{a}{q_i} (\mbox{mod }a) \end{equation*} 對於所有互質的 $x,y$ 皆成立。 由 Bezout 引理, 存在 $\frac{a}{q_i}$ 的整係數線性組合等於 $1$。 因此, 存在 $F_{q_i}$ 的整係數線性組合 $F$ 使得 $F(x,y) \equiv 1 (\mbox{mod }a)$ 對所有互質的 $x,y$ 皆成立。 而基於 $F_{q_i}$ 皆為齊次且次數相等, $F$ 必為齊次多項式, 故命題一證畢。$\Box$ 評註： 本題介於數論與代數之間, 雖為第六題, 但難度上並不如第三題, 甚至與第五題某種程度上在伯仲之間。 數奧近年來二三五六題的難度變化是值得關注的重點。 ---本工作小組係由教育部委託國立中央大學, 於「中華民國參加 2017 年亞太數學暨國際數學奧林匹亞競賽計畫」下成立。 本文的主要作者為高竹嵐助理教授, 任教國立交通大學統計學研究所--- |
2017年9月 41卷3期
2017 年第58 屆國際數學奧林匹亞競賽試題解答
