Problem 952

解：若 $n$ 為奇數，則 $m = n - 3$；若 $n$ 為偶數，則 $m = n - 2$。

1. 首先證明 $n$ 為奇數的狀況。

a. Claim. 正 $n$ 邊形內的任兩條對角線不垂直。
假設對角線 $\overline{AB}$ 和 $\overline{CD}$ 垂直。做 $AB$ 中垂線, 交此正 $n$ 邊形於頂點 $E$ (注意到 $n$ 為奇數, 故 $E$ 存在。) 令 $E'$ 為正 $n$ 邊形上 $E$ 的對稱點:
- 注意到 $n$ 為奇數, 故 $E'$ 必不是正 $n$ 邊形的頂點。
- 然而由對稱性, 易知 $\overline{EC} = \overline{E'D}$. 這代表 $E'$ 必須是正 $n$ 邊形的頂點。
矛盾!

b. 由以上 Claim 及題設, 這 $m$ 條對角線在多邊形內部必不相交; 換言之, 它們都必須從同一端點出發, 而同一端點出發的對角線共有 $n-3$ 條, 得證。

(a) 我們首先用歸納法證明一個更強的結果：對於所有 $n$, 如果我們可以從圓內接 $n$ 邊形中選出滿足題意的 $m$ 條對角線, 則 $m \le 2$. $n = 3$ 時顯然。現在, 假設 $m \le n-2$ 對 $n = 1, 2, \dots, N-1$ 都成立, 則當 $n = N$, 分成兩個 Case 討論:

Case 1. 這 $m$ 條對角線中, 有一條沒有和任何其他條在多邊形內部相交。該對角線將正 $n$ 邊形分割成一個 $n_1$ 邊形與一個 $n_2$ 邊形 ($n_1 + n_2 = n + 2$). 不失一般性, 假設 $n_1$ 邊形全部落在正 $n$ 邊形外接圓 $\Gamma$ 某條直徑的一側, 則易知該 $n_1$ 邊形內的對角線都不可能垂直, 因此在 $n_1$ 邊形內只能選擇不相交的對角線。同前面 1.(a) 的討論, 這個的最大可能是 $n_1 - 3$ 條。
另一方面, 由歸納假設, $n_2$ 內最多只能選 $m(n_2) \le n_2 - 2$ 條, 故總共至多只能選 $(n_1 - 3) + (n_2 - 2) + 1 = n - 2$ 條。

Case 2. 這 $m$ 條對角線中任一條都至少和另一條垂直。令 $d_1$ 和 $d_2$ 為其中一對垂直的對角線, 則它們將圓切成四區:


- 若有另一條對角線 $d'$, 它與 $d_1$ 或 $d_2$ 都不垂直, 則它的兩端點必然同屬於其中一區 (否則它會和 $d_1$ 或 $d_2$ 相交。)
- 若我們取另兩條相交的對角線 $d'_1$ 和 $d'_2$, 它們都不垂直 $d_1$ 或 $d_2$, 則它們的端點都必須落在同一區。然而, 易見若兩條對角線的端點都在同一區, 它們不可能垂直 (如圖), 矛盾。

- 又基於我們假設這 $m$ 條對角線中任一條都至少和另一條垂直, 故這 $m$ 條都只能平行 $d_1$ 或 $d_2$.
現在, 令 $d_1^*$ 為這 $m$ 條對角線中, 平行 $d_1$ 且長度最長者; 易知其他 $m-1$ 條對角線都不能和 $d_1^*$ 共享端點。同理, 令 $d_2^*$ 為這 $m$ 條對角線中, 平行 $d_2$ 且長度最長者; 易知其他 $m-1$ 條對角線都不能和 $d_2^*$ 共享端點。扣除 $d_1^*$ 和 $d_2^*$ 的四個端點, 其餘 $n-4$ 個頂點, 每個都最多只能是兩條對角線的端點 (因為這些對角線都必須平行 $d_1$ 或 $d_2$), 故最多只能選到
$$\frac{1}{2}(2(n-4)) + 2 = n - 2$$
對角線。得證。

(b) 最後, 我們構造 $m = n - 2$ 的選法: 選擇正 $n$ 邊形的兩對點 $A$ 和 $A'$. 選取:
- $\overline{AA'}$;
- 令 $B$ 和 $B'$ 為 $A'$ 左右的兩頂點。選取 $\overline{AB}$, $\overline{AB'}$ 和 $\overline{BB'}$, 其中 $\overline{BB'}$ 與 $\overline{AA'}$ 垂直。
- 令 $C$ 和 $C'$ 為 $A$ 左右的兩頂點。對於所有剩下的頂點
$$D \notin \{A, A', B, B', C, C'\},$$
選取 $\overline{AD}$.
以上共 $1+3+(n-2) = n-2$ 條。