IMO2006 Problem 6

2006年の国際数学オリンピックで次の定理を証明させる問題が出題されています。

定理凸多角形 $P$ の各辺にその辺を一辺とする $P$ に含まれる三角形のうち面積が最大となるものを割り当てる。このとき、割り当てられた三角形の面積の全ての辺に対する総和は $P$ の面積の二倍以上である。

その証明を始めてみたときに何か芸術作品を目の当たりにしたかのような感覚に襲われました。この記事ではその証明を鑑賞しようと思います。多角形は同じ記号で集合(多角形の辺上および内部の点全体)を表してよいことにします。また、絶対値記号でその多角形の面積を表します。

補題面積 $S$ の凸 $2n$ 角形 $P$ を考える。このとき、 $P$ の辺と頂点を一つずつ選んで出来る三角形であって面積が $S/n$ 以上であるようなものが存在する。

証明. $P$ の頂点に $A_1, \dots, A_{2n}$ と名前を付ける*1。 $P$ を二つの凸 $(n+1)$ 角形に分割する $A_kA_{k+n}$ という形の対角線を主対角線と呼ぶ。各辺 $A_kA_{k+1}$ に対して、その辺と二つの主対角線 $A_kA_{k+n}, A_{k+1}A_{k+1+n}$ の交点から得られる三角形 $\Delta(A_kA_{k+1})$ を割り当てる。

主張: $\displaystyle \bigcup_{k=1}^{2n}\Delta(A_kA_{k+1})$ は $P$ を含む。

主張の証明: $\Delta(A_kA_{k+1})$ の定義から、 $P$ の辺上および内部の点 $X$ であってどの主対角線上にもないものを任意にとったときに、 $X$ が或る $\Delta(A_kA_{k+1})$ に含まれることを示せば十分である。 $X$ が有向線分 $\overrightarrow{A_1A_{n+1}}$ の左側にあると仮定する(右側にある場合も同様に示せる)。このとき、 $X$ は有向線分 $\overrightarrow{A_{n+1}A_1}$ の右側にあるので、東大の碁石の問題と同じ考え方によって、或る $1 \leq k \leq n$ が存在して $X$ は $\overrightarrow{A_{k}A_{k+n}}$ の左側、 $\overrightarrow{A_{k+1}A_{k+1+n}}$ の右側にあることがわかる。すると、 $X \in \Delta(A_{k+n}A_{k+1+n})$ であることがわかる。主張の証明終わり.

主張より、鳩ノ巣原理によって

$\displaystyle \left|\Delta(A_kA_{k+1})\right|+\left|\Delta(A_{k+n}A_{k+n+1})\right| \geq \frac{S}{n}$

であるような $k$ が存在する。主対角線 $A_kA_{k+n}, A_{k+1}A_{k+1+n}$ の交点を $B$ とし、辺の長さについて $A_{k+1}B \geq A_{k+n+1}B$ であると仮定する(逆の場合も同様)。このとき、

$\displaystyle \left|A_kA_{k+1}A_{k+n}\right| = \left|A_kA_{k+1}B\right|+\left|BA_{k+1}A_{k+n}\right| \geq \left|\Delta(A_kA_{k+1})\right|+\left|\Delta(A_{k+n}A_{k+n+1})\right| \geq \frac{S}{n}$

となるので、三角形 $A_kA_{k+1}A_{k+n}$ が所望のものである。 Q.E.D.

定理の証明

$P$ を $\left|P\right|=S$ なる凸 $N$ 角形とし、辺に $b_1, \dots, b_N$ と名前を付ける。各 $b_i$ に対して定理の主張で割り当てられる三角形の面積を $S_i$ とする。背理法で主張を証明するため、

$\displaystyle \sum_{i=1}^N\frac{S_i}{S} < 2$

であると仮定する。このとき、有理数 $q_1, \dots, q_N$ であって

$\displaystyle \sum_{i=1}^Nq_i = 2, \quad q_i > \frac{S_i}{S} \ (i=1, \dots, N)$

を満たすようなものが存在する。 $q_1, \dots, q_N$ の分母の最小公倍数を $n$ として各 $q_i$ を $q_i=\frac{k_i}{n}$ と分数表示する。このとき、

$\displaystyle \sum_{i=1}^Nk_i=2n$

である。さて、各辺 $b_i$ を $k_i$ 等分して、 $P$ を $2n$ 角形とみなす( $180^{\circ}$ を凸多角形の内角として認める。そうしても補題は成り立つ)。すると、補題よりこの $2n$ 角形の或る辺 $b$ と頂点 $A$ が存在して、 $b$ と $A$ から定まる三角形の面積 $T$ は $\frac{S}{n}$ 以上となる。