鸽巢原理

PopHirasawa 2022-01-10 01:10:00
Categories: > Tags:

内容

鸽巢原理及其一些推论,包括但不限于


简单形式

n+1个物品放入n个盒子中,至少存在一个盒子中存在多个物品

可以抽象表示为:

令X,Y为两有限集,令f为一个从X到Y的函数

然后就可以发展出一些应用了


推论:中国剩余定理

令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个点的无向完全图,将边染成两种颜色。那么必定存在一个三角形三条边为相同的颜色。

K6K3,K3也可以表示为K_6\rightarrow K_3,K_3

更一般的定义如下:

m,n为两个不小于2的整数,那么将存在一个正整数p,令$$K_P \rightarrow K_m,K_n$$

Ramsey数r(m,n)为令等式成立的最小整数p

有定理

r(2,n)=n以及r(m,2)=m

可以往更高维推广。。。