美術館定理を示す機会があったので色々調べたところネット記事には行間を十分埋めているものが確認したところなかったので高校生でも読めるようにきちんとした証明を書いてみました。
ここは分かっている人は読み飛ばしていい。
自然数$n$に関する条件$P_{n}$から作られる全称命題
\begin{align*}
任意の自然数nに対し, P_{n}
\end{align*}
が成り立つことを示すために以下の方法がある。
このような証明方法を数学的帰納法という。
自然数$n$に関する条件$P_{n}$から作られる全称命題
\begin{align*}
任意の自然数n対し, P_{n}
\end{align*}
が成り立つことを示すために以下の方法がある。
命題$P$が真であることを証明するために, $P$が成り立たない、つまり命題「$P$でない」が成り立つと仮定して、矛盾が導かれることを示す、という方法。矛盾とは, ある命題$P$とその否定命題「$P$ でない」が同時に真であることをいう
まず断っておくこととして, この記事での多角形は凸多角形と凹多角形の両方を指します。高校までは多角形と書いたら凸多角形しか指さないですが本記事ではそうすることにします。それと美術館定理の主張以降は度数法ではなく弧度法を用います。
$n$角形でできている美術館に$360^{\circ}$見渡せる監視カメラをいくつか設置して美術館全体を監視できるようにしたい。このとき$ \left[\dfrac{n}{3}\right]$台あれば十分である。ただし,実数$x$に対し$[x]$は$x$を超えない最大の整数を表す。すなわち$[\quad ]$はガウス記号。
具体例を出して説明しないとわからないと思うので, 例を出してみます。
この美術館は1つのカメラですべてを見渡せます。
カメラ1だけでは青色で囲んだ領域までしか見渡せない。
では, この定理を色々なことを認めながら証明していきます。
まず最初に
$n\geqq{4}$ならば$n$角形は$n-3$本の対角線をうまく選んで$n-2$個の三角形に分割できる。
という定理を認めます。これは凸多角形の場合に限定すると自明ですね。凹多角形が面倒。
三角形分割の例
さらに, 多角形の各頂点に赤, 青, 緑のいづれかを塗ってみるにします。ただし, 隣り合う頂点は異なる色でそしてどの色も一回は使うことにします。このような塗り方で多角形の各頂点に色を塗ることを三彩色するということにします。
三彩色の例
三彩色ではない彩色の例(赤が隣合っている)
どんな多角形も三彩色できます。なぜなら, $n$角形$\mathrm{A_{1}A_{2}\cdots{A}}_{n}$が与えられたら, 頂点$\mathrm{A_{1}, A_{2}, \cdots, {A}}_{n-1}$には赤, 青を交互に塗り, $\mathrm{A}_{n}$には緑を塗ることで三彩色の一つが得られるからです。以下が$n=5$の例
三彩色は可能であることの図($n=5$)
では, 美術館定理の証明のために多角形にもう少し厳しい三彩色ができることを認めてみます。
$n\geqq{4}$とする。$n$角形を$n-2$個の三角形で分割する。この各三角形が三彩色された$n$角形を三彩色する方法が存在する。
定理6の特別な三彩色の例
では美術館定理を証明してみましょう。
$n$角形を三彩色してみます。するとどの色かは分からないけど, 少なくとも一つの色は$\left[\dfrac{n}{3}\right]$個以下の頂点にしか彩色していません。なぜならどの色も$\left[\dfrac{n}{3}\right]+1$個以上の頂点に彩色していると仮定すると
\begin{align*}
3\left(\left[\dfrac{n}{3}\right]+1\right)>n
\end{align*}
となりそんな三彩色の方法は存在ないので矛盾(背理法を用いている)。ここで三彩色と言っても定理3の三彩色を$n$角形にしていると仮定します。どの色かは分からないけど$\left[\dfrac{n}{3}\right]$個以下の頂点にしか彩色していない色があるので, その各頂点に監視カメラを設置してみます。すると, 各監視カメラは(美術館全体を見渡すことはできないかもしれないけど)その監視カメラが置かれている頂点をもつ(三角形分割で作られた)三角形の領域では完全に見渡すことができます。したがって, 今置いたすべての監視カメラで美術館全体を見渡すことができます。
美術館定理解決の図(この場合はどの色にカメラを設置してよい)
定理6の特別な三彩色の例として紹介した例では赤にカメラを設置すればよい
まず三角形分割の方から示そう。
$n$角形の内角の大きさの和は$(n-2)\pi$である。
$n$角形の外角の大きさの和は$2\pi$である。それゆえ内角の大きさの和は$n\pi-2\pi=(n-2)\pi$である。この式の意味は, $n\pi$は各頂点の内角と外角の大きさの和が$\pi$であることと頂点が$n$個であることと, そこから外角の大きさの和$=2\pi$を引いていることから来ている。
両端を含まない線分を開線分という。多角形$P$の連続する3つの頂点$\mathrm{A, B, C}$に対し, 開線分$\mathrm{AC}$が$P$の内部に含まれるとき, $\triangle{\mathrm{ABC}}$を$P$の耳という。
例を見てみましょう。
凸四角形とその耳
凹四角形とその耳
この凹四角形に対し以下の周を緑で塗った三角形は耳ではありません。
凹四角形とその耳でない三角形
$n\geqq{4}$なら, $n$角形は(辺は共有することは
あってもそこに目を瞑れば)互いに重なり合わない耳を2つ以上持つ。
例を見てみます。
どの2つの耳も辺は共有することはあっても互いに重なり合っていない。
互いに重なり合ってしまっている耳たち
$n=4$のときは上記の例で見たように成り立ちます。2つ以上の内角の大きさが$\pi$より大きくなることはありません。それはそのような四角形が存在すると仮定すると内角の和が$2\pi$より大きくなり命題7(内角の和の大きさの和の公式)と矛盾するからです。
$n\leqq{k}$のとき成り立つと仮定する。$k+1$多角形$P$とその内角の中で大きさが$\pi$未満のものの1つを$\angle{\mathrm{B}}$とし, その両隣の頂点をそれぞれ$\mathrm{A, C}$とする。
これを利用すると
$n\geqq{4}$ならば$n$角形は$n-3$本の対角線をうまく選んで$n-2$個の三角形に分割できる
を帰納法で得ることができる。
$n\geqq{4}$とする。$n$角形を$n-2$個の三角形で分割する。この各三角形が三彩色された$n$角形を三彩色する方法が存在する。
$n=4$のときは上述の例で述べたように成り立つ。
$n={k}$のとき成り立つと仮定して, $k+1$角形でも成り立つことを示す。$P$を$k+1$角形とする。三角形分割する。$P$の耳の一つを任意にとる。すると$P$は, この耳と$P$からそれを除いた$k$角形からなる図形だと思える。その$k$角形は帰納法の仮定から定理10(定理6)に書いてある三彩色ができるので, そのような彩色をする。$P$は任意に取った耳の一つの頂点のみまだ彩色していないので
その頂点の両隣と異なる色を塗る。この塗り方は, 定理10(定理6)に書いてある$P$に対しての彩色の一つである。よって, $n=k+1$のときも成り立つ。
以上から, 定理10(定理6)が成り立つ。
耳定理は参考にした本の記述が曖昧でちょっと修正しているのでもしかすると間違っているかもしれない。意外とこういう定理でさえ行間を埋めるのって大変だし, ネットくらいだと行間を全て埋め切った証明を中々見つけられないものですね。