每日一题[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$ 个红色三角形，命题得证．