内容
鸽巢原理及其一些推论,包括但不限于
- 简单形式
- 中国剩余定理
- 加强形式
- 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
可以往更高维推广。。。