INTEGERS

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

凸多角形を分割したときの小凸多角形の辺数の平均について

整数整数-6

問凸 $n$ 角形( $3 \leq n \leq 7$ )を二つ以上の凸多角形に分割するとき、各小多角形の辺の数の平均は $6$ より小さいことを示せ。

解答分割の個数を $k$ とし、分割によってできる平面グラフの頂点数を $v$ , 辺数を $e$ とする。このとき、面数は $k+1$ なので、Eulerの定理より

$v-e+(k+1)=2, \quad v=e-k+1$

が成り立つ。次数が $2$ であるような頂点の個数を $m$ とする( $m \leq n$ )。グラフの各頂点の次数の総和は $2e$ なので、

$2m+3(v-m) \leq 2e, \quad m \geq 3v-2e$

と評価できる。凸 $n$ 角形の外領域の境界上の辺の数を $l$ , 各小多角形の辺の数の平均を $a$ とすると、

$ka+l=2e$

であり、凸 $n$ 角形の外領域の境界上に次数が $3$ 以上の頂点が少なくとも二つはあるので、 $m \leq l-2$ である。以上より、

$2m \geq 6v-4e=6(e-k+1)-4e =ka+l-6k+6$

となって、

$k(a-6) \leq 2m-l-6 \leq m-8 \leq n-8$

が得られる。 $n \leq 7$ なので、 $a < 6$ でなければならない。 Q.E.D.