给定正整数k,对于一条由k条线段组成的不自交的折线(相邻的两条线段不共线).考虑每条线段所在的直线,求这样的直线条数的最小值.
以下回答引用自GPT:
考虑一条 k 条线段组成的不自交折线，如果我们画出这条折线并对其进行标号，将第一条线段标记为 1，第二条线段标记为 2，以此类推，最后一条线段标记为 k。同时我们将这些线段所在的直线称为 L1, L2, ..., Lm，那么显然 Lm 是我们需要的最后一条直线。
现在我们来证明，对于 i ∈ {1, 2, ..., k-1}，都存在一个整数 ni，使得与线段 i 相关联的 m - ni + 1 条直线包含了前 i 条线段。进一步地，我们可以证明当 i = k - 1 时，ni = 1 恰好满足上述条件。
为了方便起见，我们将一条线段及其左边部分的短线段称为一段。那么对于第一段，其包含了线段 1。现在我们假设已经找到了第 i-1 段，并且对于第 i-1 段，在其中已经包含了前 i-1 条线段。
接下来我们来考虑第 i 条线段。由于相邻的两条线段不共线，因此第 i 条线段必定与它之前的线段在平面上将其所处的位置分隔开。如果我们获得到这个分割线，我们便可以将第 i 条线段划分到第 m - ni + 1 条直线上，使得前 i 条线段都被这些直线所覆盖。
通过反证法，我们可以证明在不少于 m - ni 条直线的情况下并不能将 i 条线段及其之前的线段完全覆盖，因此 ni 恰好满足上述条件。而对于 i = k - 1 的情况，由于最后一条线段必然与之前的线段在平面上将其所处的位置分隔开，因此我们只需要一条直线便能将其所覆盖到。
综上所述，所有相邻的区间中至少有一个整数 n_i，满足与第 i 条线段相关联的 m - n_i + 1 条直线即可覆盖前 i 条线段。考虑覆盖整个折线所需的最小直线数量位于 {m-ni+1} 中的最小值，即为所求的答案。
因此，我们可以采用从第一条线段开始，逐一寻找这样的 ni 值来计算出答案。