每日一题[1645]红色三角形

平面上 $2n$ 个点($n>1$,$n \in \mathbb N$),无三点共线,任意两点间连线段,将其中任意 $n^2+1$ 条线段染成红色.求证:三边都为红色的三角形至少有 $n$ 个.

解析

我们称三边均为红色的三角形为红色三角形,首先证明一定存在红色三角形.设从定点 $A$ 出发的红色线段最多,由 $A$ 引出的红色线段为 $AB_1,AB_2,\cdots,AB_k$,则 $k\geqslant n+1$.若 $B_1,B_2,\cdots,B_k$ 中存在两点,不妨设为 $B_1,B_2$,使线段 $B_1B_2$ 为红色线段,则 $\triangle AB_1B_2$ 为红色三角形.若 $B_1,B_2,\cdots,B_k$ 相互之间没有红色线段相连,则从 $B_i$($i=1,2,\cdots,k$)出发的红色线段最多为 $2n-k$ 条,所以这 $2n$ 个点红色线段最多有\[\dfrac 12(k+k(2n-k)+(2n-1-k)k)=k(2n-k)\leqslant n^2<n^2+1,\]矛盾.所以存在以 $A$ 为顶点的红色三角形.接下来对 $n$ 进行归纳.

归纳基础    当 $n=2$ 时,平面上有四个点 $A,B,C,D$ 中两两连线共有 $6$ 条,其中 $5$ 条为红色,只有一条为非红色,设为 $AB$,则 $\triangle ACD$ 和 $\triangle BCD$ 均为红色三角形,命题成立.

递推证明    假设 $n=k$ 时,命题成立,即至少存在 $k$ 个红色三角形.则当 $n=k+1$ 时,有 $2k+2$ 个点,且有 $(k+1)^2+1$ 条红色线段,一定存在一个红色三角形,设为 $\triangle ABC$.考查从 $A,B,C$ 引出的红色线段分别为 $d(A),d(B),d(C)$ 条,不妨设 $d(A)\leqslant d(B)\leqslant d(C)$.

情形一    若 $d(A)+d(B)\leqslant 2k+2$,则除去点 $A,B$,剩下的 $2k$ 个点之间至少有\[(k+1)^2+1-(2k+1)=k^2+1\]条红色线段.由归纳假设可知存在至少 $k$ 个红色三角形,再加上 $\triangle ABC$,至少有 $k+1$ 个红色三角形.

情形二    若 $d(A)+d(B)\geqslant 2k+3$,则\[d(A)+d(B)+d(C)\geqslant 3k+5,\]故从 $A,B,C$ 出发向其他 $2k-1$ 个点引出红色线段至少有 $3k-1$ 条.因为 $(3k-1)-(2k-1)=k$,这 $3k-1$ 条线段至少有 $k$ 对线段有公共点(不包括 $A,B,C$),故至少存在 $k$ 个红色三角形,再加上 $\triangle ABC$,则至少有 $k+1$ 个红色三角形,所以 $n=k+1$ 时,命题也成立.

综上所述,当 $n>1,n\in\mathbb N$ 时,$2n$ 个点之间的 $n^2+1$ 条红色线段至少可组成 $n$ 个红色三角形,命题得证.

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

发表回复