第二章
抽屉原理
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 (奇数)\)的抽屉,对于每个抽屉具有互相整除关系....