不想复习。。。记录一下 https://proofsfromthebook.github.io/25 前半部分的有趣问题

pigeonhole principle https://en.wikipedia.org/wiki/Pigeonhole_principle

(1) 1，2，3，4，...，2n 中选 n+1 个， 一定有两个互质

(资料图)

(2) 1，2，3，4，...，2n 中选 n+1 个， 一定存在两个元素,a,b, a|b

看起来就不那么显然了。 把1，2，3，4，...，2n 中的所有数字写成a=b*2^k. b是奇数。b有n种可能，而我们选择了n+1个元素。

(3) 一个有nm+1个数的sequence，没有任何两个数字相等。下面两种情况至少满足其一：

- 存在长度为m+1的上升子序列

- 存在长度为n+1的下降子序列

看起来也不是那么明显了。假设序列中不存在长度为m+1的上升子序列。定义一个映射，from 序列中的每个元素 {a_1,a_2,.... , a_{mn+1} } to {1,2,...,m}，表示以一个元素开始的最长上升子序列的长度. 存在某个 s \in  {1,2,...,m}  序列中有至少n+1个元素开头的最长上升子序列(LIS)长度都是s. 把这些LIS长度都是s的元素取出来形成新的子序列，可以发现相邻两个元素一定是前者小于后者（否则LIS的长度会变成s+1）因此这是一个长度至少是n+1的下降子序列。

(4) 完全图的维数 dim(K_n)在这里的定义是：选择 [n] (n>=3)的m个排列，满足对于任意三个不同的元素a,b,c在这m个排列中都存在某个排列使得c 在 a,b 的后面。dim(K_n)=满足条件的最小的m

wiki上说的定义怎么和这里不一样。。。

https://en.wikipedia.org/wiki/Dimension_(graph_theory)

书中用巧妙的方法证明dim(K_n)>= log_2 log_2 n     就是使用了p次(3)