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

本屆試題中, 第一、 六題的領域為組合、 第二題為幾何、 第三、 四題為數論, 第五題為代數。 對此次我國代表團所翻譯成正體中文版的 6 道 IMO 試題提供參考解答, 以供國內相關學者、 數學教師等輔導數學資優生之研究、 應用與參考。

問題 1： 平面上, 如果一條直線與 $x$ 軸、 $y$ 軸、直線 $x \!+\! y \!=\! 0$ 都不平行, 則我們稱它為陽光的。
給定整數 $n \geqslant 3$。 試決定所有非負整數 $k$, 使得平面上存在 $n$ 條不同的直線滿足下列兩條件：
$\bullet$ 對於所有滿足 $a + b \leqslant n + 1$ 的正整數 $a, b$, 點 $(a,b)$ 落在這些直線中的至少一條上。
$\bullet$ 這 $n$ 條直線中恰有 $k$ 條是陽光的。

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

對任意正整數 $n \geqslant 3$, $k$ 的所有可能值為 $0$, $1$, $3$。

證明： 若一條直線不是陽光的, 就稱它是陰暗的。 如果滿足題目裡第一個條件 $n$ 條直線中恰有 $k$ 條是陽光的, 就稱 $(n,k)$ 為合格數對。 設 $S_n$ 為第一個條件中指定的點 $(a,b)$。 令 $T$ 為 $x=1$, $y=1$, $x+y=n+1$ 這三條直線形成的三角形。

引理： 設 $n \geqslant 4$。 $(n,k)$ 為合格數對的充要條件是 $(n-1,k)$ 是合格數對。

引理證明：

若 $(n-1,k)$ 是合格數對, 表示存在 $n-1$ 條直線覆蓋 $S_{n-1}$, 其中恰有 $k$ 條是陽光的。 現在再加上陰暗的直線 $x+y=n+1$。 明顯看出 $S_n$ 被這 $n$ 條直線覆蓋, 其中恰有 $k$ 條是陽光的。 所以 $(n,k)$ 也是合格數對。

另一方面, 設 $n \geqslant 4$ 且 $(n,k)$ 為合格數對。 注意到三角形 $T$ 中有 $3n-3$ 個點在 $S_n$ 中, 而 $3n - 3 \gt 2n$。 因此, 如果有 $n$ 條直線覆蓋 $S_n$, 則由鴿籠原理知道其中必有一條直線與 $T$ 的交點至少有三個。 記該直線為 $\ell$, 事實上 $\ell$ 會包含 $T$ 的一邊, 因此它是陰暗的。 所以從這 $n$ 條直線中扣掉 $\ell$ 不會改變其中陽光直線的條數。 而從 $S_n$ 中移除 $\ell$ 上的點, 恰好就是 $S_{n-1}$ 的一個平移。 因此 $(n-1,k)$ 也是合格數對。 引理證明完畢。

$\Box$

根據此引理, $k$ 的可能值與 $n$ 無關, 所以只需考慮 $n=3$ 的情形就足夠了。 下面是 $k = 0, 1, 3$ 的建構, 見圖1。
$\bullet$ $k=0$： 取直線 $y=0$, $y=1$, $y=2$。
$\bullet$ $k=1$： 取直線 $y=0$, $y=1$, 及任何一條通過 $(2,0)$ 的陽光直線。
$\bullet$ $k=3$： 取直線 $x=y$, $2x+y=2$, $x+2y=2$。

以下我們說明 $(3,2)$ 不是合格數對。 因為三條直線中恰有一條是陰暗的, 由對稱性可設其為 $x+y=4$。 剩下的三點 $(1,1)$, $(1,2)$, $(2,1)$ 必須由兩條陽光線覆蓋。 根據鴿籠原理, 此三點中至少有兩點落在其中一條陽光線。 但是這三點中任意兩點連線都是陰暗的, 故上述為不可能。證明完畢。

$\Box$

評註： 本題屬初等的組合題, 敘述平易近人。一般同學很容易想到使用數學歸納法來證明, 將維度 $n$ 降至 3, 就能以試誤法來窮舉所有可能情況。作為高中課堂上數學歸納法證明的練習寫作, 也是十分適合的。

問題 2：

設 $\Omega$ 與 $\Gamma$ 分別是以 $M, N$ 為圓心的圓, 且圓 $\Omega$ 的半徑小於圓 $\Gamma$ 的半徑。 設兩圓 $\Omega$ 與 $\Gamma$ 交於相異兩點 $A$, $B$。 直線 $MN$ 與圓 $\Omega$ 交於點 $C$, 且與圓 $\Gamma$ 交於點 $D$, 且 $C, M, N, D$ 四點以此順序落在該直線上。 令點 $P$ 為三角形 $ACD$ 的外心。 直線 $AP$ 與圓 $\Omega$ 再交於 $E \ne A$, 且直線 $AP$ 與圓 $\Gamma$ 再交於 $F \ne A$。 令點 $H$ 為三角形 $PMN$ 的垂心。

證明： 通過 $H$ 且平行於 $AP$ 的直線, 與三角形 $BEF$ 的外接圓相切。
(三角形的垂心指的是其三條高的交點。)

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

設 $T$ 為直線 $ME$ 和 $NF$ 的交點。我們將首先證明圓 $BFE$ 經過點 $T$, 然後證明直線 $TH$ 平行於 $AP$ 且與圓 $BFE$ 相切。

我們有 $\angle CPA = 2\angle CDA = \angle BDA = \angle BFA$, 所以我們得出 $PC \parallel FB$。 同樣地, $PD \parallel BE$。 我們也有 $\angle EFT = \angle NAP = \angle PDN = \angle MCP = \angle PAM = \angle MEA = \angle TEF$, 所以我們得到 $\triangle EFT$ 和 $\triangle DCP$ 都是等腰三角形且 $\triangle EFT \sim \triangle DCP$。

由於 $\angle FTE = \angle CPD = 180^\circ - \angle EBF$, 我們得到點 $B$、$F$、$T$、$E$ 共圓。 在圓 $BFTE$ 中, 直線 $BT$ 平分 $\angle EBF$, 並且等腰三角形 $CDP$ 的邊 $CD$ 平行於 $\angle CPD$ 的外角平分線。 這意味著 $BT \parallel CD$。

由 $\angle CPH = \frac{1}{2}\angle CPD = \frac{1}{2}(\angle CPA + \angle APD) = \angle MPA + \angle APN = \angle MPN$, 我們得到 $\angle CPM = \angle HPN$。 因此,

$$ \angle NMT = \angle BTM = \angle BFE = \angle CPA = 2\angle CPM = 2\angle HPN = 2\angle NMH, $$

且 $MH$ 平分 $\angle NMT$。 同樣地, 我們得到 $NH$ 平分 $\angle TNM$。

因此 $H$ 是 $\triangle MTN$ 的內心, 且 $TH$ 平分 $\angle MTN$。 所以, 在等腰三角形 $EFT$ 中, 線段 $TH$ 平行於直線 $AEFP$ 且與圓 $EFT$ 相切。

$\Box$

評註： 本題屬中等難度的幾何題。證明的關鍵在點出所問直線與圓的切點 $T$, 而這個點又有許多的定義方法。 在採取任一種定義後, 再去證明這個點該有的性質, 從而得證。 以往我國選手在幾何題的表現在世界中是亮眼的, 但近年來成績有下滑的趨勢。 今年的國手只有三位採傳統幾何作法, 而有一位採取解析幾何, 以代數求解的策略得證。 未來我們的培訓要重拾基礎幾何的訓練, 以期掌握我們較有把握的領域。

問題 3： 設 $\mathbb{N}$ 為正整數所成的集合。 定義函數 $f : \mathbb{N} \to \mathbb{N}$ 稱為包好的, 如果

$$ f(a) \quad \text{整除} \quad b^a - f(b)^{f(a)} $$

對所有正整數 $a, b$ 均成立。

試找出最小的實數常數 $c$, 使得 $f(n) \!\leqslant\! cn$ 對任意包好的函數$f$以及任意正整數$n$皆成立。

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

本題答案是 $c=4$。

證明： 證明分成兩部分。 首先我們證明 $c \leqslant 4$。 注意到 $f(n) = n$ 對所有 $n$ 成立的這個函數滿足題設, 所以它是一個包好的函數, 且 $f(n) = n \leqslant 4n$。 以下證明皆假設：存在一正整數 $m$ 滿足 $f(m) \ne m$。

將題目的整除條件記為 $P(a,b)$, 並設 $f$ 是包好的函數。 代入 $P(a,a)$ 可得 $f(a) \mid a^a - f(a)^{f(a)}$, 立得 $f(a) \mid a^a$。 所以 $f(1) = 1$, 且當 $a=p$ 時, 上式可推得 $f(p) \mid p^p$, 也就是說, $f(p)$ 為 $p$ 的冪次。

引理 1： 若 $p$ 為質數且 $f(n) \ne n$, 則 $f(p) = 1$ 或者 $p \mid n - f(n)$。

引理 1 證明： 考慮 $P(p,n)$, 即 $f(p) \mid n^p - f(n)^{f(p)}$。 若 $f(p) \ne 1$, 則由於 $f(p)$ 是 $p$ 的冪次, 有 $p \mid f(p)$, 並推得

$$ p \mid n^p - f(n)^{f(p)}. $$

由費馬小定理知 $n^p \equiv n \pmod{p}$。 並且由於 $f(p)$ 是 $p$ 的冪次, 重複使用費馬小定理也得 $f(n)^{f(p)} \equiv f(n) \pmod{p}$。 故 $p \mid n - f(p)$, 引理 1 成立。

$\Box$

當 $q$ 為質數並滿足 $q \gt |m-f(m)|$ 時, 令 $p=q$ 及 $n=m$ 代入引理 1 得 $q \mid m - f(m)$, 矛盾。 故此情形下有 $f(q) = 1$。 換句話說, 當質數 $q$ 足夠大時, 都有 $f(q) = 1$。

引理 2： 對任意奇質數 $p$, 都有 $f(p) = 1$。

引理 2 證明： 由前段文字知 $f(q) = 1$ 對足夠大的奇質數 $q$ 均成立。 取這樣的一個 $q$, 顯然有 $f(q) \ne q$。 令 $n=q$ 代入引理 1, 得到對奇質數 $p$, 有 $f(p) = 1$ 或 $q \equiv f(q) = 1 \pmod{p}$。 由狄利克雷 Dirichlet 定理知有無窮多個質數 $q$ 滿足 $q \not\equiv 1 \pmod{p}$, 所以取足夠大的這樣一個質數 $q$, 就可以由引理 1 得到 $f(p) = 1$。

$\Box$

對於任意正整數 $n \in \mathbb{N}$, 有 $f(n) \mid n^n$, 於是每個 $f(n)$ 的質因數都是 $n$ 的質因數。 取 $n$ 的奇質因數 $q$, 考慮 $P(n, q)$ 及 $f(q) = 1$, 得

$$ f(n) \mid q^n - 1, $$

即 $q$ 並不整除 $f(n)$。 所以 $f(n)$ 的質因數只可能有 $2$。 故對任意正整數 $n \in \mathbb{N}$, $f(n)$ 都是 2 的冪次, 且當 $n$ 為奇數時有 $f(n) = 1$。

設 $a = 2^x y$, 其中 $x \geqslant 0$ 且 $y$ 為奇數。則存在 $z \geqslant 0$ 使得 $f(a) = 2^z$。 我們宣稱 $z \leqslant x + 2$, 從而 $f(a) = f(2^x y) = 2^z \leqslant 2^{x+2} \leqslant 4 \cdot 2^x y = 4a$, 即 $f(n) \leqslant 4n$ 對任意正整數 $n$ 均成立, 故得 $c \leqslant 4$。 取奇數 $b$, 代入 $P(a,b)$ 可得

$$ 2^z \mid b^{2^x y} - 1, \quad \text{即} \quad b^{2^x y} \equiv 1 \pmod{2^z}. $$

令 $\phi(t)$ 代表歐拉函數, 即小於 $t$ 並與 $t$ 互質的正整數個數。 由於 $\phi(2^z)$ 是 2 的冪次且 $y$ 為奇數, 故存在正整數 $c$ 滿足 $yc \equiv 1 \pmod{\phi(2^z)}$。 取 $b = 5^c$, 則由費馬-歐拉定理得

$$ 1 \equiv b^{2^x y} = (5^{yc})^{2^x} \equiv 5^{2^x} \pmod{2^z}, $$

即 $2^z \mid 5^{2^x} - 1$。但由提升指數引理 (lifting-the-exponent, 簡稱 LTE) 可知

$$ \nu_2(5^{2^x} - 1) = \nu_2(5+1) + \nu_2(5-1) + \nu_2(2^x) - 1 = 1 + 2 + x - 1 = x + 2 $$

($\nu_2(t)$ 代表正整數 $t$ 的因數分解式中 $2$ 的冪次數), 故得 $z \leqslant x + 2$。 至此 $c \leqslant 4$ 證明完成。

最後舉一個滿足 $c = 4$ 的包好的函數的例子。 定義 $f(n)$ 如下：

$$ f(n) = \begin{cases} 1, & \text{當 $n$ 為奇數}, \\[-4pt] 2, & \text{當 $n$ 為偶數, 且 $n \ne 4$}, \\[-4pt] 16, & \text{當 $n = 4$}. \end{cases} $$

下面直接對所有正整數 $a$ 來驗證 $f$ 的性質。

$\bullet$ 若 $a$ 為奇數, 則 $f(a) = 1$, $P(a,b)$ 顯然對所有 $b$ 均成立。
$\bullet$ $a$ 為偶數但 $a \ne 4$, 此時 $f(a) = 2$。對任意正整數 $b$, 整數 $b$ 與 $f(b)$ 同奇同偶。故 $b^a - f(b)^2$ 必為偶數, $P(a,b)$ 成立。
$\bullet$ $a = 4$：此時 $f(a) = 16$。要證明的是：對任意正整數 $b$, 有 $16 \mid b^4 - f(b)^{16}$。 當 $b$ 為奇數時, $f(b) = 1$, 且 $b^4 - f(b)^{16} = b^4 - 1 = (b-1)(b+1)(b^2+1)$。注意到 $b-1$, $b+1$ 及 $b^2 + 1$ 均為偶數, 並且由於 $b-1$ 與 $b+1$ 是連續偶數, 它們之中恰有一個被 4 整除。 故 16 整除 $b^4 - 1 = b^4 - f(b)^{16}$。而當 $b$ 是偶數時, $f(b)$ 也是偶數, 故 $b^4$ 與 $f(b)^{16}$ 都是 $16$ 的倍數。檢驗完成。

所以 $f$ 是包好的函數。 並且由 $f(4) = 16$, 因此 $c = 4$ 為最佳值。 證明完畢。

$\Box$

評註： 本題其實是中等偏難的數論題, 擺在第三題似乎高估了其難度。 使用函方的標準解題步驟, 馬上就知道 $f(n)$ 的質因數必為 $n$ 的質因數, 再利用狄利克雷定理、費馬小定理與提升指數引理 (LTE), 就能完整刻劃包好的函數的行為。 本題的解題步驟中規中矩, 這也是前段國家都表現優良的原因。我國選手只有三位完全解出, 也代表我們在數論領域仍待加強。

問題 4： 正整數 $N$ 的真因數, 指的是除了 $N$ 自己之外的其他正因數。

無窮數列 $a_1, a_2, \ldots$ 由正整數組成, 其中的每一項都有至少三個真因數。 對每個 $n \geqslant 1$, 整數 $a_{n+1}$ 是 $a_n$ 最大的三個真因數之和。

試求 $a_1$ 的所有可能值。

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

此數列的初始項 $a_1$ 的所有可能值為形如 $a_1 = 12^M \cdot 6N$ 的正整數, 其中 $M, N$ 為非負整數且 $N$ 與 10 互質。

證明： 本題證明中, 因數就是正因數。令 $d_i(a)$ 表示正整數 $a$ 的第 $i$ 大的真因數。

若此數列中有一項 $a_n$ 是奇數的話, 則

$$ a_{n+1} = d_1(a_n) + d_2(a_n) + d_3(a_n) \leqslant \frac{a_n}{3} + \frac{a_n}{5} + \frac{a_n}{7} \lt a_n, $$

並且 $a_{n+1}$ 是 $a_n$ 的三個奇因數之和, 它也是奇數。 也就是說, $a_n, a_{n+1}, \dots$ 形成嚴格遞減的正整數無窮數列。 但此為不可能, 故此數列中的每一項 $a_n$ 都是偶數。

引理： 如果 $a_n$ 不是 3 的倍數的話, $a_{n+1}$ 也不是 3 的倍數。

引理證明： 我們以 $a_n$ 是否為 4 的倍數來考慮。若 $a_n$ 是 4 的倍數, 則

$$ a_{n+1} = \frac{a_n}{2} + \frac{a_n}{4} + d_3(a_n) = 3 \cdot \frac{a_n}{4} + d_3(a_n) \equiv d_3(a_n) \pmod{3}. $$

但 $d_3(a_n)$ 是 $a_n$ 的因數, 所以它不是 3 的倍數, 亦即 $a_{n+1}$ 也不是 3 的倍數。 另一方面, 如果 $a_n$ 不是 4 的倍數, 我們設 $p$ 為 $a_n$ 的最小奇質因數。 此時 $d_1(a_n) = \frac{a_n}{2}$ 為奇數、 $d_2(a_n) = \frac{a_n}{p}$ 為偶數, 故 $a_{n+1} = a_n - d_1(a_n) - d_2(a_n)$ 為奇數。 於是 $\frac{a_n}{d_3(a_n)}$ 為 $a_n$ 第二小的偶因數, 其必為 $2p$。 至此得

$$ a_{n+1} = \frac{a_n}{2} + \frac{a_n}{p} + \frac{a_n}{2p} = \frac{a_n}{2} + 3 \cdot \frac{a_n}{2p} \not\equiv 0 \pmod{3}, $$

引理至此證明完畢。

$\Box$

所以, 如果此數列有一項 $a_n$ 不是 3 的倍數的話, 有

$$ a_{n+1} = d_1(a_n) + d_2(a_n) + d_3(a_n) \leqslant \frac{a_n}{2} + \frac{a_n}{4} + \frac{a_n}{5} \lt a_n, $$

又得到一個嚴格遞減的正整數無窮數列, 不合。

到這邊, 我們已經知道此數列的每一項都是 6 的倍數。 因此,

$$ d_1(a_n) = \frac{a_n}{2}, \quad d_2(a_n) = \frac{a_n}{3}, \quad d_3(a_n) = \frac{a_n}{4} \text{ 或 } \frac{a_n}{5} \text{ 或 } \frac{a_n}{6} $$

對所有正整數 $n$ 均成立。 分成三種情形討論：
(i) 若 $a_n$ 可被 4 整除, 則 $a_{n+1} = \frac{a_n}{2} + \frac{a_n}{3} + \frac{a_n}{4} = \frac{13}{12} a_n$。
(ii) 若 $a_n$ 不被 4 整除但被 5 整除, 則 $a_{n+1} = \frac{a_n}{2} + \frac{a_n}{3} + \frac{a_n}{5} = \frac{31}{30} a_n$。這裡注意到 $a_{n+1} = \frac{31}{30} a_n$ 會是奇數, 不合。 故此情形不會發生。
(iii) 若 $a_n$ 不被 4 整除也不被 5 整除, 則 $a_{n+1} = \frac{a_n}{2} + \frac{a_n}{3} + \frac{a_n}{6} = a_n$。

注意到在上述所有情況中, 都有 $a_{n+1} \geqslant a_n$ 且 $\nu_2(a_{n+1}) \leqslant \nu_2(a_n)$ (這裡 $\nu_2(a)$ 指的是正整除 $a$ 被 2 整除的最高冪次。) 由於 $\nu_2(a_n)$ 會是一個遞減的非負整數數列, 它終究會成為常數數列。 而由上段的討論知道 $\nu_2(a_{n+1}) = \nu_2(a_n)$ 只有在情況 (iii) 發生, 因此最終只有情況 (iii) 成立； 也就是說, 此數列從某一項開始成為常數數列： $a_L = a_{L+1} = \cdots$。 最終值 $a_L$ 是 6 的倍數, 但不被 4 或 5 整除, 故 $a_L$ 必為形如 $a_L = 6N$ 的正整數, 其中 $N$ 與 10 互質。

取 $L$ 為其最小可能值, 得 $\nu_2(a_1)\gt \nu_2(a_2) \gt \cdots \gt \nu_2(a_L) = 1$。 故當 $1 \leqslant n \leqslant L-1$ 時發生情況 (i), $a_n$ 被 4 整除且 $a_{n+1} = \frac{13}{12} a_n$。 故 $a_1 = 12^{L-1} \frac{a_L}{13^{L-1}}$ 為形如 $a_1 = 12^M \cdot 6N$ 的正整數, 其中 $M$ 為非負整數, $N$ 為正整數, 且 $N$ 與 10 互質。

代回檢查： 當 $a_1 = 12^M \cdot 6N$ 時, 有 $a_k = 12^{M+1-k} \cdot 13^{k-1} \cdot 6N$ 對 $1 \leqslant k \leqslant M+1$ 皆成立, 且 $a_{M+1} = a_{M+2} = \cdots = 13^M \cdot 6N$, 符合題意。 證明完畢。

$\Box$

評註： 本題是簡單的數論題。 首先將題目轉化成： 有哪些初始值 $a_1$ 會使此遞迴數列無限進行下去, 再調查相鄰項 $a_n$ 與 $a_{n+1}$ 的大小關係, 就能將該數列完全刻劃出來。 答案也不是立即可以猜到的, 是道很有創意的數論題。只要是具有國中程度的同學, 都可以試著練習看看。

問題 5： 某甲與某乙玩一個雙人遊戲, 其規則依賴於某個雙方都知道的正實數$\lambda$。 在此遊戲的第 $n$ 輪 (從 $n=1$ 開始), 採取以下動作：

$\bullet$ 當 $n$ 為奇數時, 甲選一個非負實數 $x_n$ 滿足 $$ x_1 + x_2 + \cdots + x_n \leqslant \lambda n. $$ $\bullet$ 當 $n$ 為偶數時, 乙選一個非負實數 $x_n$ 滿足 $$ x_1^2 + x_2^2 + \cdots + x_n^2 \leqslant n. $$

當其中某位玩家不能選出滿足條件的數字 $x_n$ 時, 遊戲立即結束, 並宣告另一名玩家獲勝。 如果此遊戲可以無限進行下去, 則兩人皆不算獲勝。 雙方都知道挑出來的數字。

試找出使甲有必勝策略的所有 $\lambda$ 值, 也找出使乙有必勝策略的所有 $\lambda$ 值。

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

$\bullet$ 當 $\lambda \gt \frac{1}{\sqrt{2}}$ 時, 甲有必勝策略。
$\bullet$ 當 $\lambda \lt \frac{1}{\sqrt{2}}$ 時, 乙有必勝策略。
$\bullet$ 當 $\lambda = \frac{1}{\sqrt{2}}$ 時, 兩人都沒有必勝策略。

證明： 我們將全部證明分成以下三個區塊。

(a) 我們先證明： 當 $\lambda \lt \frac{1}{\sqrt{2}}$ 時, 乙有必勝策略。 事實上, 在乙的每一輪都可以選最大的實數, 亦即對每一個正整數 $k$, 令

$$ x_{2k} = \sqrt{ 2 - x_{2k-1}^2 }. $$

我們將說明此策略可以保證乙不敗, 並且在足夠多輪之後甲選不出他需要的數字。

在第一輪, 甲選了非負實數 $x_1$ 滿足 $x_1 \leqslant \lambda \lt \frac{1}{\sqrt{2}}$。 於是 $2 - x_1^2 \geqslant 0$, 乙可以選 $x_2 = \sqrt{2 - x^2}$, 此保證 $x_1^2 + x_2^2 = 2$。 在第三輪, 甲要選非負實數 $x_3$ 滿足 $x_1 + x_2 + x^3 \leqslant 3\lambda$。 甲選不出來就乙勝, 否則甲可以選的最大實數 $x_3$ 滿足

$$ x_3 \leqslant 3 \lambda - x_1 - \sqrt{2 - x_1^2} \leqslant 3\lambda - \sqrt{2} \lt \lambda. $$

這裡用到當 $x \in [0, \sqrt{2}]$ 時, 不等式 $x + \sqrt{2 - x^2} \geqslant \sqrt{2}$ 成立, 可由不等式兩邊平方證明之。 由於 $x_3 \lt \lambda$, 所以 $2 - x_3^2 \geqslant 0$, 乙就可以選 $x_4 = \sqrt{2 - x_3^2}$ 了。依此類推, 只要乙持續選取 $x_{2k} = \sqrt{2 - x_{2k-1}^2}$, 就可以保證甲輸或者甲選出的下一個數字保持 $x_{2k+1} \lt \lambda$, 然後乙又有合法的選擇了。 換句話說, 只要乙選 $x_{2k} = \sqrt{2 - x_{2k-1}^2}$, 就有

$$ x_1 + x_2 + \cdots + x_{2k} = \sum_{i=1}^k \left( x_{2i-1} + \sqrt{2 - x_{2i-1}^2} \right) \geqslant 2k \cdot \frac{1}{\sqrt{2}}, $$

此時仍然使用不等式 $x + \sqrt{2-x^2} \geqslant \sqrt{2}$。當 $\lambda \lt \frac{1}{\sqrt{2}}$ 時, 存在足夠大的正整數 $k$ 滿足 $k \sqrt{2} \gt \lambda (2k+1)$, 甲就在第 $2k+1$ 輪時因為沒得選了而落敗, 此時乙獲勝。

(b) 接下來我們描述 $\lambda \gt \frac{1}{\sqrt{2}}$ 時甲的必勝策略。 甲的策略其實是在前面的好多輪都選 0, 然後在足夠多輪後選一個很大的數字讓乙在下一輪選不下去。 以下是這個策略可行的細節。

首先我們說明甲總是可以在他的每一輪都選 0。 顯然在第一輪是可行的。 如果到第 $2k$ 輪時, 甲選了 $x_1 = x_3 = \cdots = x_{2k-1} = 0$, 則由柯西不等式得

$$ x_1 + x_2 + \cdots + x_{2k} = x_2 + x_4 + \cdots + x_{2k} \leqslant \sqrt{k (x_2^2 + x_4^2 + \cdots + x_{2k}^2) }. $$

若乙此時尚未落敗, 則由規則知 $x_2^2 + x_4^2 + \cdots + x_{2k}^2 \leqslant 2k$, 因此代回上面的不等式可得

$$ x_1 + x_2 + \cdots + x_{2k} \leqslant \sqrt{2} \cdot k \lt \lambda \cdot 2k, $$

所以甲總是可以在第 $2k+1$ 輪選 $x_{2k+1} = 0$。事實上, 甲可以選擇任何滿足下列不等式的非負實數 $x_{2k+1}$：

$$ x_{2k+1} \leqslant \lambda (2k+1) - k \sqrt{2} = k (2 \lambda - \sqrt{2}) + \lambda. $$

注意到因為 $\lambda \gt \frac{1}{\sqrt{2}}$, 上面不等式的最右邊可以到任意大。

現在, 取正整數 $\ell$ 足夠大來滿足下式：

$$ \frac{ \ell \sqrt{2} + \sqrt{2\ell + 2} }{ 2 \ell + 1 } \lt \lambda. $$

由於 $\lambda \gt \frac{1}{\sqrt{2}}$, 這樣的 $\ell$ 必定存在。 甲的策略就是在第 1, 3, $\dots$, $2\ell - 1$ 輪時都選 $0$, 而在第 $2\ell + 1$ 輪時選 $x_{2\ell + 1} = \lambda (2\ell + 1) - \ell \sqrt{2}$。 我們已經說明這些選擇都是可行的, 而由 $\ell$ 與 $x_{2\ell+1}$ 的定義知

$$ x_1^2 + x_2^2 + \cdots + x_{2\ell+1}^2 \geqslant x_{2\ell + 1}^2 = \left( \lambda (2\ell+1) - \ell \sqrt{2} \right)^2 \gt 2 \ell + 2, $$

所以在第 $2\ell+2$ 輪時乙沒有非負實數可選而落敗。

(c) 最後我們說明當 $\lambda = \frac{1}{\sqrt{2}}$ 時雙方都立於不敗之地。 由 (a) 的討論知道乙在第 $2k$ 輪總是可以選擇 $x_{2k} = \sqrt{2 - x_{2k-1}^2}$, 而由 (b) 的討論知道甲總是可以在第 $2k+1$ 輪選 $x_{2k+1} = 0$, 故雙方皆不敗。 本題證明完畢。

$\Box$

評註： 將代數不等式以對戰遊戲的形式包裝出來, 是本題的巧思。 首先要觀察試驗出參數 $\lambda$ 的關鍵臨界值, 此值在幾次嘗試後不難得出, 並且雙方的不敗策略也會跟著自然出現。 最後是分析兩者的必勝策略, 其中用到的不等式也是基本的。 可謂是一種新的題目設計方向。

問題 6： 考慮由單位方格組成的 $2025 \times 2025$ 網格。 豆哥想把一些長方形磁磚放在這個網格上, 使得每塊磁磚的各邊落在格線上, 且每個單位方格最多被一塊磁磚覆蓋。 磁磚的大小可能不同。

若豆哥要讓每一行及每一列都恰有一個單位方格不被磁磚覆蓋, 試求他所需使用磁磚的最小數量。

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

豆哥需要至少 $2025 + 2 \times 45 - 3 = 2112$ 塊磁磚。

證明： 我們將考慮更一般的 $n \times n$ 網格的情況, 其中 $n = k^2$ 是完全平方數 (就本題而言, 取 $k = 45$ 及 $n = 2025$)。 我們將證明答案為 $k^2 + 2k - 3$。 我們先給建構。 考慮 $k=4$ 的一種建構方式, 如圖2 所示。 其中中間有 $(k-1)^2$ 塊磁磚, 並在四周各有 $k-1$ 塊磁磚, 故磁磚總數為 $(k-1)^2 + 4(k-1) = k^2 + 2k - 3$。

對於下界, 考慮任意一種磁磚配置, 並將每個未覆蓋的方格標上 $\sf{X}$。 用四塊 $n \times 1$ 的磁磚圍繞在原本的網格周圍。

定義一條「上升路徑」, 是沿著磁磚邊緣行走且僅向上和向右的路徑；這裡我們允許長度為零的路徑。 設 $x_1, x_2, \ldots, x_m$ 為 $\sf{X}$ 方格中具有下列性質的最長子序列：

$\bullet$ 存在一條上升路徑, 從網格的左下角連到 $x_1$ 的左下角。
$\bullet$ 對於每個 $i = 1, 2, \ldots, m-1$, 存在一條上升路徑從 $x_i$ 的右上角連到 $x_{i+1}$ 的左下角。
$\bullet$ 存在一條上升路徑, 從 $x_m$ 的右上角連到網格的右上角。

這些上升路徑以及 $x_1, x_2, \ldots, x_m$ 共同組成了一道「大堡礁」, 將網格劃分為兩個區域。 設 $\mathcal{U}$ 為在上半區域的 $\sf{X}$ 方格所成集合, $\mathcal{L}$ 為在下半區域的 $\sf{X}$ 方格所成集合, 且 $\mathcal{X}$ 為 $\{x_1, x_2, \ldots, x_m\}$, 即位於大堡礁上的 $\sf{X}$ 方格。 $\mathcal{U}$、 $\mathcal{L}$ 和 $\mathcal{X}$ 構成所有 $\sf{X}$ 方格的分割。

對於每個 $\sf{X} \in \mathcal{X} \cup \mathcal{L}$, 我們將其與右方以及下方的兩塊磁磚連接。 這樣會產生若干個不相交的「下鏈」。由於每個 $\sf{X}$ 僅與兩塊磁磚連接, 且每塊磁磚最多僅與兩個 $\sf{X}$ 連接, 每一條鏈必定在磁磚及 $\sf{X}$ 中交替。 又因為鏈中 $\sf{X}$ 方格形成遞增序列（即每個 $\sf{X}$ 方格一定在前一個的右上方）, 所以不可能有迴路。 也就是說, 每條鏈的第一個及最後一個都必然是磁磚。 最後, 鏈中所有磁磚都必然位於下半區域, 因為它們不可以跨越大堡礁。

同理, 對於每個 $\sf{X} \in \mathcal{X} \cup \mathcal{U}$, 我們將其與左方以及上方的兩塊磁磚連接。 這樣也會產生若干個不相交的「上鏈」, 其中所有磁磚都在上半區域。同理, 上鏈有與下鏈類似的性質。 上下鏈之間必定互不相交, 唯一的例外是 $\mathcal{X}$ 上的 $\sf{X}$ 方格。 圖 3 展示了這道大堡礁上 $\mathcal{X}$ 的情形。

引理： 每一條鏈至多包含 $m$ 個 $\sf{X}$ 方格。

引理證明： 假設有一條由 $y_1, y_2, \dots, y_\ell$ 的 $\sf{X}$ 方格組成的鏈, 其中 $\ell \gt m$。 我們將證明這些 $\sf{X}$ 可以用於建構一個更長的大堡礁, 這與 $m$ 的最大性不合。

根據鏈的構造方式, 對於 $i = 1, 2, \dots, \ell-1$, 在鏈中的 $y_i$ 與 $y_{i+1}$ 之間存在一條上升路徑。 為了找出從網格左下角到 $y_1$ 左下角的連通上升路徑, 注意到在長方形磁磚中, 從某個頂點出發總可以往下或往左走。 因此, 我們可以從 $y_1$ 左下角開始, 不斷往下或往左, 直到抵達網格左下角。 同理, $y_m$ 的右上角也總可以連接至網格右上角的一條上升路徑。

因此, 我們構造出了一個包含超過 $m$ 個 $\sf{X}$ 方格的更長的大堡礁, 此為矛盾。

$\Box$

我們回到上下鏈。 $\mathcal{U} \cup \mathcal{L}$ 中的每個 $\sf{X}$ 方格恰好屬於一條鏈, 而 $\mathcal{X}$ 中的每個 $\sf{X}$ 方格恰好屬於兩條鏈。 將 $\mathcal{X}$ 中的 $\sf{X}$ 方格算作兩次, 我們共計有 $m + k^2$ 個 $\sf{X}$ 方格。 根據上述引理, 每條鏈最多有 $m$ 個 $\sf{X}$ 方格, 因此鏈的數目至少為 $(m + k^2)/m = 1 + k^2/m$ 條。 由於每條鏈中磁磚數剛好比 $\sf{X}$ 方格數多一, 且不同鏈包含不同的磚塊, 故至少有

$$ (m + k^2) + \left(1 + \frac{k^2}{m}\right) = k^2 + \left(m + \frac{k^2}{m}\right) + 1 \geqslant k^2 + 2k + 1 $$

個磁磚。 去除最初外部加的四個磁磚, 則至少還剩下 $k^2 + 2k - 3$ 個磁磚, 證明完畢。

$\Box$

評註： 本題是本屆賽事中最艱難的題目, 全場只有 6 名選手獲得滿分。 其中所需磁磚最小數量的建構方式, 巧妙地運用了 2025 為平方數的性質。 但即使如此, 該建構方式也只提供了其證明的一個小提示。如何正確地標示其中的組合物件, 並詳述其性質, 再處理其中的不等式問題, 都是本題的困難點。 打 $\sf{X}$ 的格子的配置可以看成一個排列, 此問題對於排列的統計量研究, 提供了一個新的想法。

本工作小組係由教育部委託國立台灣師範大學, 於「中華民國參加 2025 年第 37 屆亞太數學、 第 14 屆歐洲女子數學及第 66 屆國際數學奧林匹亞競賽計畫」下成立。 本文的主要作者為林延輯副教授, 任教於國立台灣師範大學數學系。