書記が数学やるだけ#669 タイルの敷き詰めと分割の例

平面充填問題の導入として，ピックの定理と美術館定理について見ていく。

問題

ピックの定理を格子点の個数と面積の関係から求めてみる。

説明

一つの図形で平面を覆うことができるかどうか，さまざまな方向から考えられてきた。

解答

(i)では円の内部にある数を不等式で評価し，挟み撃ちにより極限を示す。

(ii)では円に交わる数で不等式を立てる。

(iii)では格子店の個数から不等式を立てる。

上をまとめると格子平行四辺形の面積が1で，それを半分割した三角形の面積が1/2であることがわかる。

ピックの定理の証明では，上に示した三角形への分解を用いる。ポイントは分割した多角形を平面グラフと見なすことであり，グラフ理論の性質から数を絞ることができる。

もう一つ応用として美術館定理を扱う。これも三角形への分解と平面グラフ化を利用する。ここで3色彩色を行うと，各色がカメラの位置を示すことになり，その数が必要なカメラの台数となる。

本記事のもくじはこちら：