Problem 1
如若这种情况下，存在两条相交的线段，如下图所示，设 AC, BD 交点为 O，由于无三点共线情况，必然有 B 和 O 不重合
这表明新的连线方案，总长度之和小于原本的方案，矛盾！因此这种方案下不存在线段相交，亦即题目所求
Problem 2
Task 1
在
Task 2
由于三次函数
满足以下性质：
不存在直线与其有大于等于四个交点（代数基本定理）。
任意在其上的三个点，他们共线当且仅当他们的横坐标之和为
故考虑如下的构造方式：
若
下面对这种构造方式的 magic line 数进行分析：
对于奇数情况，
为 偶 数 为 奇 数 与
\begin{cases}
k/2 \sim k/2-1 \sim -(k+1) & (k \text{ 为偶数}) \
(k+3)/2 \sim (k-1)/2 \sim -(k+1) & (k \text{ 为奇数})
\end{cases}
为 奇 数 时 共 条 ， 为 偶 数 时 共 条 。 而 由 初 始 情 况 ， 时 有 条 ， 时 有 条 ， 故 时 有 ： \frac{k^2}{2} = \frac{(n - 1)^2}{8} \text{ 条（} k \text{ 为偶数）}
\frac{k^2 + 1}{2} = \frac{(n-1)^2}{8} + \frac{1}{2} \text{ 条（} k \text{ 为奇数）}
即 不 小 于 条 。 则 偶 数 情 况 时 在 奇 数 情 况 下 去 掉 了 ： \begin{cases}
-k/2 \sim -k/2 - 1 \sim k+1 & (k \text{ 为偶数}) \
-(k+3)/2 \sim -(k-1)/2 \sim k+1 & (k \text{ 为奇数})
\end{cases}
You can't use 'macro parameter character #' in math mode 至多不超过 $\frac{k+1}{2}$ 条边，即 $n = 2k$ 时，magic line 条数至少有 $$\frac{k^2}{2} - \frac{k+1}{2} = \frac{n^2 - 2n - 4}{8}$$ 条。 综上，通过这样的构造，我们可以得到 $M_n$ 的一个 lower bound 为 $$\boxed{M_n \geq \frac{n^2 - 2n - 4}{8}}$$ ![[Pasted image 20251123215329.png]] ## Problem 3 ![[Pasted image 20251123154805.png]] 考虑 $$i \in ([n] \cap (\underset{F \in \mathcal{F}}{\cap}F)$$ 令 $\mathcal{F'}$ 为包含 i 的所有子集即可 ## Problem 4 ![[Pasted image 20251123154829.png]] 由题意，注意到 n 个点中的每条连线，必然出现在这些图的唯一一个之中，亦即 n 个点的任意一个点对，存在在这些图的点集的唯一一个之中（这一转换由原图和子图都是完全图得到），这把问题化归为课上的 Theorem 9.6，得到 $m \geq n$ 
对任意给定的染色情况，考虑所有红蓝配对连线的方案中，连线线段长度之和最短的情况。
考虑将 AC BD 改为 A 与 BD中的红点相连，C 与 BD 中的蓝点相连，不妨就设为 AB，CD 建边。则由三角形边长公式