初中题：证明存在三条线段可构成三角形

gxqcn

有10条线段，长度均大于1且小于55，
证明：必可从中选出3条线段，使之可构成一个三角形。

Lwins_G

\[ F_{10} = 55. \]

gxqcn

hujunhua

一行字的回帖就占了近20行的高度，太浪费页面空间了。左边栏头像下方的内容是不是太占高度了，可否放在头像的mouse停留弹出框里？

dianyancao

是不是我理解有问题，线段长度：
\(1,1,2,2,4,4,8,8,16,16\)
怎么选择三条线段构成三角形啊
哦，是不是线段的总和长度小于55

这样用反证法就找不到反例了

dianyancao

用\(x_i\)表示线段长度,将线段长度排序，即
\(1 < \cdots \leq x_i \leq \cdots \leq x_j \leq \cdots \leq x_k \leq \cdots <55 \)
假设没有任何三条线段能构成三角形,
那么对于任意的\(i < j < k \),有\(x_i+x_j \leq x_k\),只需\(x_k \ge x_{k-2}+x_{k-1}\)即可
即任意给定\((x_i,x_j)\),那么\(x_k\)不能位于禁止区间\([x_{k-1},x_{k-2}+x_{k-1})\)内,否则构成三角形
而\(x_k\)影响的禁止区间为\([x_{k+1},x_{k}+x_{k+1})\)
所以最小化每个\(x_k\),能最小化禁止区间的总长度

现在用贪婪法，求出\(x_k\)的禁止区间总长度所能达到的最小值
先取\((x_1,x_2)\)，那么产生的禁止区间为\([x_2,x_1+x_2)\)
要使禁止区间的总长度最小化，那么\((x_1,x_2) \to (1,1)\)
因为若\((x_1,x_2)\)不位于\((1,1) \)处，
那么总是可以唯一的将\((x_1,x_2)\)调整到区间的左边端点\((1,1)\)处，使得禁止区间\([x_2,x_1+x_2)\)的长度不变或减小,
接着,选择\(x_3\),应使得\(x_3 \ge x_2+x_1\),要使得\(x_3\)影响的禁止区间\([x_4,x_3+x_4)\)长度最小，只能取\(x_3=x_2+x_1\)
同理,选择\(x_k\),应使得\(x_k \ge x_{k-2}+x_{k-1}\)，要使得\(x_k\)影响的禁止区间\([x_{k+1},x_{k}+x_{k+1})\)长度最小化，
只能取：
\(x_k = x_{k-2}+x_{k-1}\)

上式为斐波那契数列，由此得:
\[\begin{align*}x_1&=1,&x_2&=1,&x_3&=2,&x_4&=3,&x_5&=5, \\
x_6&=8,&x_7&=13,&x_8&=21,&x_9&=34,&x_{10}&=55.\end{align*}\]
产生的禁止区间为\([1,55]\),其总长度能取到的最小值为\(55-1=54\)
即不会构成三角形的必要条件是线段长度区间长度\(\ge 54\)，
而题目条件中给出的线段长度区间为\((1,55)\),其区间长度\(<54 \)
所以存在一条线段，其长度在禁止区间中，能找到解

gxqcn

可以稍简短点。仍用反证法。
将10条线段长度从小到大排列，依次为：\(1\lt x_1\leqslant x_2\leqslant \dots\leqslant x_{10}\lt55\)，
三线段可构成三角形三边，其充要条件是：最长的小于另两条长度之和。
假设不存在可构成三角形三边的三线段，则必有：
\(x_1 \gt 1, \\
x_2 \geqslant x_1 \gt 1, \\
x_3 \geqslant x_2 + x_1 \gt 2, \\
x_4 \geqslant x_3 + x_2 \gt 3, \\
x_5 \geqslant x_4 + x_3 \gt 5, \\
\qquad\cdots \\
x_{10} \geqslant x_9 + x_8 \gt 55\) 这与 \(x_{10} \lt 55\) 相矛盾，所以假设不成立，证毕。

gxqcn

可以把命题加强一点（但会更多地暴露问题本质）：
有 \(n\;(n\geqslant3)\) 条线段，如果最长线段的长度小于最短线段的 \(F_n\) 倍，则必可从中选出三条线段，使之可构成一个三角形。
注：\(F_n\) 表示第 \(n\) 项 Fibonacci 数列（\(F_0=0,\;F_1=1,\;F_n=F_{n-1}+F_{n-2}\pod{n\in \ZZ}\)）。