内容
鸽巢原理及其一些推论，包括但不限于
- 简单形式
- 中国剩余定理
- 加强形式
- Ramesy定理
- 呃呃
简单形式
n+1个物品放入n个盒子中，至少存在一个盒子中存在多个物品
可以抽象表示为:
令X，Y为两有限集，令f为一个从X到Y的函数
- 若X的元素大于Y的元素，则f不是一对一的
- 若X和Y有相同个数的元素，且f是映上的，则f是一对一的
- 若X和Y有相同个数的元素，且f是一对一的，则f是映上的
然后就可以发展出一些应用了
推论：中国剩余定理
令m和n为互素的正整数，有正整数a、b，且a不大于m-1，b不大于n-1。则存在x，x mod m = a，x mod n = b。
证明：先得出在a，a+m，a+2m，…(n-1)m+a中mod n没有相同的余数。因此n个数中0到n-1每个数都作为余数出现。那对与b也存在对应的p令pm+a mod n = b
Ramsey定理
在6个人中，或有三个人他们彼此互相都认识，或有三个人，他们中两两都彼此不认识。
也就是说：
考虑一个6个点的无向完全图，将边染成两种颜色。那么必定存在一个三角形三条边为相同的颜色。
也可以表示为
更一般的定义如下：
m，n为两个不小于2的整数，那么将存在一个正整数p，令$$K_P \rightarrow K_m,K_n$$
Ramsey数r(m,n)为令等式成立的最小整数p
有定理
r(2,n)=n以及r(m,2)=m
可以往更高维推广。。。