每日一题[1679]剖分

凸 $n$ 边形及 $n-3$ 条在 $n$ 边形内不相交的对角线组成的图形称为一个剖分图.求证:当且仅当 $3\mid n$ 时,存在一个剖分图是可以一笔划的圈(即可以从一个顶点出发,经过图中各线段恰一次,最后回到出发点).

解析

因为 $n-3$ 条在形内互不相交的对角线将凸 $n$ 边形分为 $n-2$ 个顶点均是 $n$ 边形顶点的小区域,每个区域的内角和不小于 $\mathrm \pi$,$n$ 边形的内角和为 $\left(n-2\right)\mathrm \pi$,所以每个小区域都是三角形.

必要性     用归纳法容易证明可将每个三角形区域涂成白蓝两色之一,使得有公共边的三角形不同色.假设已按照这样的要求染色,由于剖分图为可以一笔画的圈,所以由每个顶点引出的线段都是偶数条.从而每个顶点都是奇数个三角形的顶点,因此以原多边形外边界为一边的三角形区域有着相同的颜色,不妨设为白色;另一方面,剖分图的每条对角线都是两种不同颜色三角形的公共边,所以设白三角形有 $m_1$ 个,蓝三角形有 $m_2$ 个,则\[n=3m_1-3m_2\implies 3\mid n.\]

充分性    设 $n=3m$,多边形为 $A_1A_2\cdots A_{3m}$,连接 $3m-3$ 条对接线,形成 $m-1$ 个三角形 $A_1A_{3i}A_{3i+2}$($i=1,2,\cdots,m-1$),然后由 $A_1$ 出发,依次走过这些三角形,再走过凸多边形的外边界即可一笔画并回到初始点 $A_1$,命题得证.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论