Problem 1

对，考虑每个顶点对应

由于顶点的 isolate 性质等价于与其他 n - 1 个点不建边，故

令，其中为变量，则

故只要趋向，则，即无 isolate point 的概率趋向 1

另一方面，若趋向，使用矩方法

p.s. 注意这里不是

由前面的讨论可知

而

故

由不等式知此时，综上证毕

Problem 2

将问题转化为对不同 pubs 进行三染色的问题。考虑对每个 pub 进行随机的三染色（分别对应第 1, 2, 3 天）

则由于每个人愿望中的各不相同，故其不被满足的概率为

另一方面，考虑对给定的人，与之被满足概率不独立的人数：不独立的必要条件是出现了同样的 pub name，而这至多有人。

考虑 Lovasz Local Lemma：

注意到

故存在一种三染色使得所有人都被满足，即证

k-uniform k-regular 超图的每条超边显然至多与条超边有交，故若

由 Lovasz Local Lemma 即得可二染色。而时，，又左侧增速小于右侧，已知上式成立可二染色

考虑中所有长度为的等差数列，每个等差数列在随机的二染色下同色的概率为

另一方面，注意到两个这样的等差数列同色概率不独立当且仅当这两个数列至少共享两个数字，下面对给定的等差数列计算一个不独立数列数量的上界

考虑一个与其不独立的数列，首先由的大小知，的公差至多为，而对于每个固定的公差，通过枚举 “A 与 B 最左侧匹配点分别对应 A 与 B 中第几项”，至多能够对应出一个满足的

而如果的第个匹配了的第一项，最终只会有一个匹配项，这表明至多有个满足要求的

因此，若

由 Lovasz Local Lemma 知二染色下存在全部长度为的等差数列均不同色的概率不为 0