每日一题[1734]递推递归

将一个凸 $2019$ 边形的每条边任意染成红、绿、蓝三种颜色之一,每种颜色的边各 $673$ 条.证明:可作这个凸 $2019$ 边形的 $2016$ 条在内部互不相交的对角线,将其剖分成 $2017$ 个三角形,并将所作的每条对角线也染为红、绿、黄三种颜色之一,使得每个三角形的三条边或者颜色全部线条相同,或者颜色互不相同.

解析    我们证明一个加强的命题.

引理    若凸 $n$($n\geqslant 5$)边形的每条边染为 $a,b,c$ 的三种颜色之一,且每种颜色都只至少有一条边,那么存在符合要求的剖分.

归纳基础    不妨设 $a,b,c$ 三种颜色的边数依次不减,则当 $n=5$ 时只可能为 $abccc$ 和 $abbcc$,剖分方式如图.

递推证明    若命题对 $n$ 成立,考虑 $n+1$ 的情形.在凸 $n+1$ 边形中,如果存在两条相邻的边为相同颜色,则用对角线将这两条相邻的同色的边形成三条边颜色都相同的三角形,则问题转化为 $n$ 的情形;如果不存在两条相邻的边为相同颜色,则必然存在两条相邻边为不同颜色,且这两种颜色的边的数目都不小于 $2$,否则设去掉那条颜色与众不同的边(记为 $a$ 颜色)以及与之相邻的两边,剩下的 $n-2$ 条边必然为 $b,c$ 交替,由于 $n\geqslant 5$,于是 $b,c$ 颜色的边都至少有 $2$ 条.此时用对角线将这两条不同色的边形成三条边颜色都不相同的三角形,则问题转化为 $n$ 的情形. 综上所述,原命题得证.

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

发表评论