杂题选讲

杂题选记

写一点比较神奇的杂题。觉得出的都很有心意啊。

抽屉原理

抽屉原理通常不会在程序中出现，但是这是一个评价复杂度，人肉计算阈值的有时不错的方法。

如果你要学习一些十分厉害的抽屉原理，可以翻 高中奥林匹克小丛书 · 组合数学 的第二章，上面写着一些比较复杂的抽屉。

\(Ramsey\) 定理

虽然这和 “图论” 有关，但是和真正 \(\texttt{OI}\) 里面的图论大有不同。好像这也是一种组合数学的应用吧。

定理内容：一个六阶完全图 \(K_6\)，一定会存在一个同色、大小为 \(3\) 的环。

证明：

考虑抽屉原理。

点 \(A\) 会向外射出 \(5\) 条线。由抽屉原理可知，其中会有三条线同色。不妨设这三条线分别是 \(AB\) , \(AC\) , \(AD.\) 在 \(\triangle BCD\)，一定会有一个与 \(AB, AC, AD\) 同色的线段，不妨设这条线段是 \(AB\) ，则 \(\triangle ABC\) 一定是同色三角形。

扩展：

我们记最少的一定存在一个大小为 \(k\) 的环的最小完全图为 \(R_k\) 阶完全图，由上述结论可知： \(R_{3} = 6\), \(R_4=17,R_6=65, \cdots\)，之后并不好计算的。

如果有兴趣可以做一做这个 \(\texttt{NP-Hard?}\)

杂题 \(1\)

现在有 \(n\) 个数，请你找到两个子集，并且使他们的和相等。

\(n\leq 10^5\)

答案

如果 \(n\leq 22\)，那么你一定会做的，对吗？

那么就让我们证明 \(n\leq 22\) 和 \(n \leq 10^5\) 是同样的吧。

\(22\) 个数一定会生成至多 \(2^{22}\) 个数，如果 \(\leq 2^{22}\) 的话，那么一定会有个相同的答案，重合部分减去就好了。而 \(2^{22} \geq 10^5\) ，所以