インテジャーズ

INTEGERS

数、特に整数に関する記事。

IMO2006 Problem 6

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

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

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

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

証明. Pの頂点にA_1, \dots, A_{2n}と名前を付ける*1Pを二つの凸(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_iq_i=\frac{k_i}{n}と分数表示する。このとき、

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

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

こうして、bを含む或る辺b_iAから出来る三角形はPに含まれるが、その面積をUとすると

\displaystyle U=k_iT \geq k_i\cdot \frac{S}{n} = q_iS > S_i

となって、S_iの最大性に矛盾する。 Q.E.D.

*1:反時計回りの順番に。また、便宜的にa \equiv b \pmod{2n}であればA_a=A_bとなるように任意の整数kに対してA_kが意味を持つようにしておく。