问题及解答

平面上 $n$ 条直线, 没有重合现象. 交点最多有多少个?

例如: 2 条直线至多有一个交点.  3 条直线至多有 3个交点.

可以证明, 平面上 $n$ 条直线至多有 $C_n^2$ 个交点.

记 $f(n)$ 为平面上 $n$ 条直线相交点的个数的最大值.

通过观察, 容易获得以下结果.

\[
\begin{aligned}
f(2)&=1,\\
f(3)&=1+2=3,\\
f(4)&=1+2+3=6,\\
&\vdots\\
\end{aligned}
\]

因此, 猜测 $f(n)$ 的公式为

\[f(n)=1+2+3+\cdots+(n-1)=\frac{n(n-1)}{2}.\]

下面通过归纳法进行证明.

Pf.  设 $k$ 条直线两两相交, 有 $C_k^2$ 个交点. 即假设 $n=k$ 时, 有 $f(k)=C_k^2=\frac{k(k-1)}{2}$.

记这 $k$ 条直线分别为 $\ell_1,\ell_2,\ldots,\ell_k$. 它们与 $x$ 轴正方向的夹角分别为 $\theta_1,\theta_2,\ldots,\theta_k$. 它们互不相同. 

取直线 $\ell_{k+1}$, 其与 $x$ 轴正方向夹角为 $\theta_{k+1}$. 只要令 $\theta_{k+1}$ 不同于上面 $k$ 个角度( $\theta_i$, $i=1,2,\ldots,k$, 那么 $\ell_{k+1}$ 就不可能将 $\ell_1,\ell_2,\ldots,\ell_k$ 完全隔开在一侧.  于是, 让 $\ell_{k+1}$ 沿垂直于 $\ell_{k+1}$ 的方向移动, 总可以到达一个位置, 使得 $\ell_{k+1}$ 与每条 $\ell_i$ ($i=1,2,\ldots,k$) 相交于新的点.

因此

\[
f(k+1)=f(k)+k=\frac{k(k-1)}{2}+k=\frac{k(k+1)}{2}.
\]

故猜测对所有正整数 $n$ 都成立.  证毕.