离散数学课堂习题及课后习题 - PPX

第二章

抽屉原理

Background:

简单形式：

把（n+1）个物体放入n个盒子，必有一个盒子中装了两个物体。其实这个也是狄利克雷描述的一个特殊的表述（如果对于一个映射$ X\to Y $ ,如果\(|X|>|Y|\),则\(f\)不可能是单射,也就是会有\(f(x_1)=f(x_2)\)），但是一般看来这些形式都比较弱，值得注意的是，狄利克雷形式给出了抽屉原理的本质，也就是对于单射的一种否定

进阶一下：

对于\(q_1,q_2,q_3 ...q_n\)为n个正整数，如果把\(\Sigma_{i}^{n}q_i-n+1\)个物体放入n个盒子中，至少有一个盒子i中放入了至少\(q_i\)个物体，这个具体的证明可以通过假设$\forall$0<i \(\leq\)n,第i个盒子中不超过\(q_i-1\)个物体,然后累加发现矛盾

平均值原理：

\(\Sigma_{1}^{n} m_i/n>k-1\),说明至少一个大于等于k，同样如果小于k说明至少一个不超过k

奇偶性原理

可以通过对于其中奇偶性的分类实现相应的考虑，奇数+奇数（偶数+偶数），偶数\(\times\)奇数....
然后对于奇数后偶数而言就有不同的数论性质，比如说偶数可以由奇数产生，这可以用来构建\(2^k (奇数)\)的抽屉，对于每个抽屉具有互相整除关系....

Questions:

1.从三的同余类建立三个抽屉，然后对于有意义的抽屉数不断分类讨论（$3\to 2 \to 1 $）然后分别使用抽屉原理

2. 通过2x2判断出坐标点的奇偶性构成\(（x,y）,x,y\in \lbrace 奇数，偶数\rbrace\),然后同类相加必定为偶数

3.我们使用这样的四个圆形区域作为抽屉的构建

4.从1,2,3，...2n中任取n+1个数则存在\(a_i|a_j\) 题目给n+1说明构建的抽屉一定是n个，那么自然就是奇偶构建抽屉，那么分别就会有\(2^k*\lbrace 奇数 \rbrace\)的抽屉,这也说明了不是每个抽屉都要很多东西，主要是多个属于一个的时候会有问题，同时所有的东西都会放到这些抽屉中来，然后会有一个n的限度，即使optimal的方式也会出现错误