45305 2021年第62屆國際數學奧林匹亞競賽試題解答
2021年第62屆國際數學奧林匹亞競賽試題解答

2021 年第 62 屆國際數學奧林匹亞競賽 (International Mathematical Olympiad, 簡稱 IMO) 由俄羅斯主辦1 1 2021年IMO原定由美國主辦, 後美國因故無法主辦, 於 2020 年九月 IMO 賽事期間向大會提出, 經大會協調後, 由 2020 年主辦國俄羅斯緊急接任。, 原定於今年七月份於聖彼得堡舉辦, 唯因全球 COVID-19 疫情緣故, 改由各參賽國各自於境內設立考試中心 (Exam Center), 由大會指派之專員 (Commissioner) 在場監督, 並由俄羅斯主辦國遠端視訊監考下進行賽事。 本屆共有 107 個國家與會、 合計 619 位學生 (含 64 位女學生) 代表參賽。

往年活動先由各參賽國 (主辦國除外) 於規定時間內提交數道試題, 再由主辦國的試題委員會 (Problem Selection Committee, 簡稱 PSC) 研究選出 30 道左右的預選試題, 分屬代數、 組合、 幾何、 數論等不同領域和不同難度的試題; 最後再經由各國領隊組成的評審會議 (Jury Meeting) 票選暨修訂出最後 6 道IMO 試題, 依主題內容及難易層次分配成兩份試題, 分別在連續的兩天舉行競試, 每天 3 道試題, 考試時間都是 4 小時又 30 分鐘。 然而今年由於遠距競賽關係, 改由 PSC、 主辦國與 IMO 委員會 (IMO Board) 先行決定題目後, 於考前三個小時以入闈方式送交各國領隊, 在該國專員監督下進行翻譯後, 在考前一個小時送交大會審查, 並於考前三十分鐘內交由專員押送至考場。 除此變動外, 考試的題目數量與時間長度與往年相同。

本屆試題第一題的領域為數論, 第二題為代數, 第三題為幾何, 第四題為幾何, 第五題為組合, 第六題為代數。 然而第一題幾乎全部是組合成分, 數論成分甚少, 甚至連整除性都沒有, 導致今年數論近乎缺席。 此外, 第一、 五、 六題之組合成分濃厚, 故又再次出現 2020 年的, 近乎有三題組合題的狀況。

更進一步地, 今年的第二題與第六題, 乃至於去年的第三題, 皆出現明顯為大學層級之內容; 對比大會規章上規範題目 ``應該涵蓋大學以前的各種數學領域'', 此一狀況令人費解。但由於近兩年在遠距競賽下, 皆為俄羅斯在未經領隊會議投票下出題, 上述關於數論、 組合與大學層級數學的狀況, 是否屬於此兩年的特例情況, 未來需要進一步觀察。

對此次我國代表團所翻譯成正體中文版的 6 道 IMO 試題提供參考解答, 以供國內相關學者、數學教師等輔導數學資優生之研究、 應用與參考。

問題一: 令 $n\geqslant100$ 為一整數。 誼廷將數字 $n, n+1,\ldots, 2n$ 各寫在一張不同的牌上。 他接著將這 $n+1$ 張牌洗牌並將它們分為兩疊。 試證明至少有一疊牌中存在兩張牌的數字總和是完全平方數。

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

注意到如果存在正整數$k$, 使得 $(a,b,c)=(2k^2-4k, 2k^2+1, 2k^2+4k)$ 都在 $n$ 到 $2n$ 之間, 由於 $a+b, a+c, b+c$ 皆為完全平方數, 且依據鴿籠原理, 必有其中兩個數在同一疊中, 因此原命題成立。 故我們只需證明, 對於所有 $n \geq 100$, 存在這樣的 $k$, 也就是滿足

\begin{equation}\label{P1} n \leq 2k^2 - 4k\quad \mbox{且}\quad 2k^2 + 4k \leq 2n \end{equation}

的 $k$。 但注意到對於所有 $k \geq 9$, 所有在區間 $I_k := [k^2+2k, 2k^2-4k]$ 內的 $n$ 皆能讓 \eqref{P1} 成立, 且由於

\begin{equation*} (k+1)^2 + 2(k+1) \leq 2k^2 - 4k, \end{equation*}

易知 $I_k$ 與 $I_{k+1}$ 重疊。 這表示 $\cup_{k=9}^\infty I_k = [99, \infty)$, 從而對於所有 $n \geq 100$, 這樣的 $k$ 都存在。 證畢。

評註: 此為一極度簡單之數論題, 基本上沒有用到任何整數性質, 只需要比較大小即可。 俄羅斯連續兩年主辦, 數論類題目大幅弱化, 今年數論更是近乎缺席狀態。

問題二: 證明不等式

\begin{equation}\label{P2} \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|} \leqslant \sum_{i=1}^n\sum_{j=1}^n \sqrt{|x_i+x_j|} \end{equation}

對於所有實數 $x_1,\dots, x_n$ 皆成立。

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

注意到若我們將所有 $x_i$ 皆平移 $t$, \eqref{P2} 左式的值不會改變, 而右式成為

\begin{equation*} H(t) := \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i + x_j +2t|}. \end{equation*}

令左式之值為 $L$, 並取充分大的 $T$ 使得 $H(T)$ 與 $H(-T)$ 皆比 $L$ 大。 注意到 $p_{ij} = -\frac{x_i+x_j}{2}$、 $T$ 與 $-T$ 將整個實數線分為若干區間 (包含 $(-\infty, -T)$ 與 $(T, \infty)$, 其中 $p_{ij}$ 不必然相異)。 此外, 由於 $f_\ell(t) := \sqrt{|\ell+2t|}$ 在 $(-\infty, -\ell/2]$ 與 $[-\ell/2, \infty)$ 上都是凹函數, 因此 $H(t)$ 在這每個區間中都是凹的。

原不等式等價於證明 $H(0) \geq L$。 令 $[a,b]$ 為其中包含 $0$ 的區間, 由 $H$ 的凹性知

\begin{equation*} H(0) \geq \min\{H(a), H(b)\} \geq \min_{ij} \{H(p_{ij}), H(T), H(-T)\}. \end{equation*}

又由於 $H(\pm T) \gt L$, 故我們僅須證明 $H(p_{ij}) \geq L$ 對於所有 $i,j$ 皆成立即可。 但注意到證明 $H(p_{ij}) \geq L$ 等價於證明 \eqref{P2} 在把 $(x_i, x_j)$ 用 $(x_i + p_{ij}, x_j + p_{ij})$ 代換下成立, 而此時有 $x_i+x_j=0$。 因此我們僅須證明當存在 $x_i+x_j=0$ 時, \eqref{P2} 會成立即可。 以下分情況討論:

  • 若 $i=j$, 則 $x_i=0$, 此時我們可以把 \eqref{P2} 左右兩邊的 $x_i$ 都移除。 這會讓 \eqref{P2} 左右都同時減去 $2 \sum_{k \neq i} \sqrt{|x_k|}$, 不影響不等號的方向。
  • 若 $i \neq j$, 則 $x_i+x_j=0$, 此時我們可以把 \eqref{P2} 左右兩邊的 $x_i$ 和 $x_j$ 都移除。 這會讓 \eqref{P2} 左右都同時減去 \begin{equation*} 2 \sqrt{2|x_i|} + 2 \sum_{k \neq i,j} \left( \sqrt{|x_k+x_i|} + \sqrt{|x_k+x_j|} \right), \end{equation*} 一樣不影響不等號的方向。

無論哪一種狀況, 都可以把 \eqref{P2} 化約成更小的 $n$ 的問題。 又基於 \eqref{P2} 在 $n=0$ 或 $1$ 時顯然成立, 故由歸納法得證。

評註: 這是一個非常困難的不等式題目, 全球平均得分僅 0.375 分, 全對者僅 16 人, 幾乎快要跟第三題的分布相同。 就分數而言, 它是史上最難的第二題, 比 2011 年的風車題還難;事實證明, 它絕對不是一道中等題目。

此題目的難處在於, piecewise 凹性是數學奧林匹亞中從未出現過的項目, 且就選手心理而言, 依照往年題目方向, 一般不等式的選題都是使用微積分方式會相對難處理的題目, 因此會預設不去走這條路; 就算在一番嘗試後決定往微積分的方向走, 在微分一次就出現不連續點時, 實在沒有理由進一步去考慮二次微分的性質。

而命題委員會之作為也令人費解。 去年第二題的不等式, 命題委員會才在評分標準上明確抵制微積分類型的解法。 然而今年, 同樣的主辦國, 卻給出如此大學層級分析手法的凹性操作題目, 甚至在官方解答中還另外提供兩個完全利用微積分進行的作法, 這之間的差異令人費解, 且影響日後選手在不等式方向上的準備。

最後, 俄羅斯連續兩年主辦皆出現不等式題目, 此與其他年份不等式題目普遍不受青睞的情況大相逕庭。

問題三: 令 $D$ 為銳角三角形 $ABC$ 的內點, 其中 $AB\gt AC$, 使得 $\angle DAB = \angle CAD$。 點 $E$ 在線段 $AC$ 上, 滿足 $\angle ADE = \angle BCD$。 點 $F$ 在線段 $AB$ 上, 滿足 $\angle FDA = \angle DBC$。 點 $X$ 則在直線 $AC$ 上, 滿足 $CX=BX$。 令 $O_1$ 與 $O_2$ 分別為三角形 $ADC$ 與 $EXD$ 的外心。 證明直線 $BC$、 $EF$ 與 $O_1O_2$ 共點。

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

令 $T$ 為 $BC$ 與 $EF$ 交點。 我們先證明 Lemma:

Lemma 1. $TD^2 = TB \times TC = TF \times TE.$

證明: 首先令 $Q$ 為 $D$ 對三角形 $ABC$ 的等角共軛點。 基於 $\angle BAD = \angle DAC$, $Q$ 在 $AD$ 直線上, 因此 $\angle QBA = \angle DBC = \angle FDA$, 因此 $QDFB$ 共圓。 同理, $QDEC$共圓。 這意味著 $AF \times AB = AD \times AQ = AE \times AC$, 從而 $BCEF$ 共圓。

我們接著證明圓 $(DEF)$ 與 $(BDC)$ 相切。 這是因為

\begin{align*} \angle BDF & = \angle AFD - \angle ABD = (180^o - \angle FAD - \angle FDA) - (\angle ABC - \angle DBC) \\[-3pt] & = 180^o - \angle FAD - \angle ABC = 180^o - \angle DAE - \angle FEA \\[-3pt] & = \angle FED + \angle ADE = \angle FED + \angle DCB, \end{align*}

故知圓 $(DEF)$ 與 $(BDC)$ 相切。

現在, 由於 $BCEF$ 共圓, 點 $T$ 對 $(BDC)$ 與 $(EDF)$ 的冪相等, 而這意味著此兩圓的根軸必通過 $T$。 又因為此兩圓相切, 其根軸必通過切點 $D$, 從而 $TD^2 = TB \times TC = TF \times TE$。 引理證畢。

$\Box$

回到原題。 令 $TA$ 交 $(ABC)$ 於另一點 $M$。 由於 $BCEF$ 共圓且 $AMCB$ 共圓, 由引理知 $TM \times TA = TF \times TE = TB \times TC = TD^2$。 這意味著 $AMEF$ 共圓。

接著注意到當我們以 $T$ 為反演中心, $TD$ 為反演半徑進行變換, $M$ 被映射到 $A$, $B$ 映射到 $C$, 從而 $(MBD)$ 被映射到 $(ADC)$。 基於此兩圓的交點 $D$ 在反演半徑上, 此兩圓的另一個交點 $K$ 也必然在反演半徑上, 故 $TK=TD$。 這表示 $T$, $(KDE)$ 圓心與 $(ADC)$ 圓心皆在 $KD$ 中垂線上。 又 $(ADC)$ 圓心為 $O_1$, 而 $O_2$ 為 $(DXE)$ 圓心, 因此我們只需證明 $KDEX$ 共圓, 則 $O_2$ 便是 $(KDE)$ 圓心, 從而 $O_1O_2$ 即過 $T$, 便證完原題。

要證明 $KDEX$ 共圓, 注意到 $BM$、 $DK$、 $AC$ 分別為 $(ABCM)$、 $(ACDK)$ 與 $(BMDK)$ 兩兩的根軸, 故此三線共點於 $P$。 此外, $M$ 位於 $(AEF)$ 上, 表示我們有

\begin{align*} \sphericalangle (EX, XB) & \!=\! \sphericalangle (CX, XB) \!=\! \sphericalangle (XC, BC) \!+\! \sphericalangle (BC, BX) \!=\! 2 \sphericalangle (AC, CB) \\[-3pt] & \!=\! \sphericalangle (AC, CB) \!+\! \sphericalangle (EF, FA) \!=\!\sphericalangle (AM, BM) \!+\! \sphericalangle (EM, MA) \!=\!\sphericalangle (EM, BM), \end{align*}

因此 $MEXB$ 共圓, 從而 $PE \times PX = PM \times PB = PK \times PD$, 故 $EKDX$ 共圓。 證畢。

$\Box$

評註: 本題為困難的幾何題, 要求對等角共軛等幾何性質有相當的理解, 且程序繁複, 關卡極多。 就題目而言是一道好的幾何題目, 尤其是以這種形式考驗選手是否有觀察出 $D$ 的等角共軛點與相關性質的部分。 然而在整體考卷的搭配上, 由於有第二題在前, 導致第一天的三題綜合難度極高且作業量極大。 命題委員顯然在此份考卷的難度與作業量預估上有所失準。

問題四: 令圓 $\Gamma$ 的圓心為 $I$, $ABCD$ 為一凸四邊形, 使得線段 $AB$, $BC$, $CD$ 和 $DA$ 皆與 $\Gamma$ 相切。 令 $\Omega$ 為三角形 $AIC$ 的外接圓。 假設 $BA$ 往 $A$ 方向的延長線交 $\Omega$ 於 $X$, 且 $BC$ 往 $C$ 方向的延長線交 $\Omega$ 於 $Z$。 $AD$ 與 $CD$ 往 $D$ 方向的延長線分別交 $\Omega$ 於 $Y$ 和 $T$。 試證

$$ AD+DT+TX+XA=CD+DY+YZ+ZC. $$

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

點 $I$ 為三角形 $TCZ$ 外角平分線和外接圓的交點, 因此 $I$ 是弧 $TCZ$ 中點, 從而 $IT=IZ$。 同理, $I$ 是弧 $YAX$ 中點, 故 $IX=IY$。 令 $O$ 為 $\omega$ 圓心, 則上述關係告訴我們 $X$ 與 $T$ 分別為 $Y$ 與 $Z$ 對 $IO$ 直線的鏡射點, 因此 $XT=YZ$。

令 $ABCD$ 內接圓分別交 $AB$、 $BC$、 $CD$、 $DA$ 於 $P$、 $Q$、 $R$、 $S$。 基於 $IP=IS$, $IX=IY$, 有三角形 $IXP$ 與 $IYS$ 全等。 同理, $IRT$ 與 $IQZ$ 全等。 結合以上兩者知 $XP=YS$ 且 $RT=QZ$。

現在, 令 $P(\mathcal{Q})$ 為 $\mathcal{Q}$ 的周長, 則基於 $AS=AP$, $CQ=RC$ 及 $SD=DR$, 我們有

\begin{align*} P(ADTX) & = XT + XA + AS + SD + DT = XT + XP + RT \\[-3pt] & = YZ + YS + QZ = YZ + YD + DR + RC + CA = P(CDYZ), \end{align*}

從而原題得證。

$\Box$

評註: 這是一個以第四題來說略為複雜的幾何題, 光是要成功尺規作圖就需要一些技巧; 相較之下, 選手甚至有機會花更短的時間就做出第五與第六題。 題目要求計算周長貌似很嚇人, 需要一些幾何觀察來將兩個周長連結在一起。

問題五: 兩隻松鼠, 阿布與阿江, 為了過冬共蒐集了 $2021$ 顆核桃。 阿江將所有核桃編號 $1$ 到 $2021$, 並繞著牠們最喜歡的樹挖了 $2021$ 個洞圍成一圈。 次日一早, 阿江注意到阿布無視編號地在每個洞裡各放了一顆核桃, 心生不悅。 阿江因此決定透過 $2021$ 次操作將核桃重排。 在第 $k$ 次操作, 阿江將與 $k$ 號核桃相鄰的兩個核桃交換位置。 證明存在一個 $k$ 使得, 在第 $k$ 次操作, 阿江交換了編號 $a$ 與 $b$ 的核桃, 其中 $a\lt k\lt b$。

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

歸謬證法, 假設原命題為否, 這表示在第 $k$ 步交換的兩顆核桃 $a$ 與 $b$, 要不都大於 $k$, 要不都小於 $k$。 若我們在第 $k$ 步把 $k$ 號核桃和其所在的洞都塗黑, 則有兩種可能的 case:

  1. 若 $a$ 與 $b$ 都 $\lt k$, 則 $a$ 與 $b$ 核桃都是黑的;
  2. 若 $a$ 與 $b$ 都 $\gt k$, 則 $a$ 與 $b$ 核桃都不是黑的。

結合以上兩點, 我們知道每次交換的兩顆核桃必然是相同顏色, 因此當一個洞被塗黑後, 它從此只能有黑核桃。 由於每次都只會增加一個黑洞與一個黑核桃, 這直接意味著每個洞恰會被當作一次交換中心。

現在假設有兩個相鄰的洞, $M$ 與 $N$, 其分別在第 $m$ 與 $n$ 次操作被塗黑, 不失一般性令 $m\lt n$。 注意到 $M$ 在第 $m$ 次已被塗黑, 所以在第 $n$ 次操作前, $M$ 裡的核桃必然已經是黑的, 也就是一顆編號小於 $n$ 的核桃。 這表示第 $n$ 次操作一定是 case 1。 同理可知第 $m$ 次操作一定是 case 2。 這表示 case 1 與 case 2 的洞一定是交替出現, 但由於 $2021$ 是奇數, 這是不可能的。 矛盾! 證畢。

$\Box$

評註:相比於第一天, 這是一題相對簡單的組合題, 題目敘述大部分都是不需要的資訊, 且解法路線眾多, 難度上甚至可以放在第四題。 這是代表隊本來的預估, 且有三位選手拿到滿分, 一位拿到六分。 然而, 全世界對這一題的解題創況卻出乎意料地差, 均分僅 2.15 分。 台灣隊在此題的表現上領先其他國家的部分與成因, 或許值得進一步探討。

問題六: 令 $m\geqslant 2$ 為一整數, $A$ 為一由有限多個整數 (不必然為正整數)所形成的集合, 且 $B_1,B_2,B_3,\ldots,B_m$ 為 $A$ 的子集。 假設對於每個 $k=1,2,\ldots, m$, $B_k$ 內元素的總和為 $m^k$。 試證 $A$ 至少包含 $m/2$ 個元素。

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

令 $A = \{a_1, \ldots, a_k\}$。 歸謬證法, 假設 $K:=|A|\lt m/2$。 定義 $s_i$ 為 $B_i$ 中元素的和, 已知 $s_i = m^i$。

讓我們考慮所有形如下式的表示式:

\begin{equation*} f(c_1, \ldots, c_m) := c_1 s_1 + \cdots + c_m s_m, ~~ c_i \in \{0, 1, \ldots, m-1\} \mbox{ for all } i = 1, \ldots, m。 \end{equation*}

上式共有 $m^m$ 種組合。 但另一方面, 注意到 $S_i$ 是 $B_i$ 的元素和, 也就是 $A$ 中某些元素的和, 而 $A$ 中的每一個元素最多可以出現在 $m$ 個 $B_i$ 中, 因此 $f(c_1, \ldots, c_m)$ 必然可以表示成

\begin{equation*} f(c_1, \ldots, c_m) = \alpha_1 a_1 + \cdots + \alpha_K a_K, ~~ \alpha_i \in \{0, 1, \ldots,m(m-1)\} \mbox{ for all } i = 1, \ldots, m. \end{equation*}

但上式最多只能給我們 $(m(m-1)+1)^K \lt m^{2K} \lt m^m$ 種組合。 這意味著存在兩個 $f(c_1, \ldots, c_m)$ 的值相同。

然而基於 $s_i=m^i$, $f(c_1, \ldots, c_m)$ 直接對整數在 $m$ 進制下的表示法, 而這個表示法是唯一的, 也就是不可能有兩個 $f(c_1, \ldots, c_m)$ 的值相同。 矛盾!

評註: 本題雖然是代數題, 但牽涉高中範圍的代數甚少, 反而牽涉較多線性代數的線性基底(或是生成函數)之概念。 搭配上 2020 年第三題明確使用大學圖論定理, 以及今年第二題使用大學分析概念, 國際數學奧林匹亞往大學數學推進是否為一競賽趨勢, 或僅為此兩年俄羅斯主辦下之特例現象, 是需要持續觀察的部分。此外, 今年的第一、五、六題皆大幅偏向組合內容, 又再次上演 2020 年題目往組合方向倒的狀況。

---本工作小組係由教育部委託國立中央大學, 於「中華民國參加 2021 年亞太數學暨國際數學奧林匹亞競賽計畫」下成立。 本文的主要作者為高竹嵐助理教授, 任教於國立陽明交通大學統計學研究所。---