2. 软件开发
    3. 鸽巢原理

    鸽巢原理

    xiaoxiao2023-10-03  145

    1. 鸽巢原理的简单形式

    设 A A A是有限集， ∣ A ∣ ⩾ n + 1 , A i ⊆ A ( i = 1 , 2 , ⋯   , n ) |A| \geqslant n+1, A_{i} \subseteq A(i=1,2, \cdots, n) ∣A∣⩾n+1,Ai​⊆A(i=1,2,⋯,n)且 ⋃ i = 1 n A i = A \bigcup_{i=1}^n A_i = A ⋃i=1n​Ai​=A，则必有正整数 k ( 1 ≤ k ≤ n ) k(1 \leq k \leq n) k(1≤k≤n)，使得 ∣ A k ∣ ≥ 2 |A_k| \geq 2 ∣Ak​∣≥2。

    2. 鸽巢原理的一般形式

    将 N N N个物体放入 K K K个盒子中，至少有一个盒子不少于 ⌈ N / K ⌉ \lceil N / K\rceil ⌈N/K⌉个物体。

    3. 鸽巢原理的广义形式

    将 ( n 1 + n 2 + ⋯ + n k − k + 1 ) (n_1+n_2+\dots+n_k-k+1) (n1​+n2​+⋯+nk​−k+1)个物体放入 k k k个盒子，则存在 i i i，第 i i i个盒子里不少于 n i n_i ni​个物体。

    4. 鸽巢原理例题

    例题一

    证明从任意给的5个整数中必能选出3个数，它们的和能被3整除。

    证明 以 A A A表示所给的5个整数所成之集，对任一整数 i ( 0 ≤ i ≤ 2 ) i(0\leq i \leq 2) i(0≤i≤2)，令 A i = { a ∣ a ∈ A 且 a 除 于 3 所 得 的 余 数 为 i } A_i = \{a|a \in A 且 a除于3所得的余数为i \} Ai​={a∣a∈A且a除于3所得的余数为i} 如果 A 0 , A 1 , A 2 A_0,A_1,A_2 A0​,A1​,A2​均不是空集，任取 a i ∈ A i a_i \in A_i ai​∈Ai​，则 a 0 + a 1 + a 2 a_0+a_1+a_2 a0​+a1​+a2​能被3整除。如果 A 0 , A 1 , A 2 A_0,A_1,A_2 A0​,A1​,A2​中有空集，去掉一个空集，设余下的两个集合为 A k A_k Ak​和 A l ( 0 ≤ k ≤ l ≤ 2 ) A_l(0 \leq k \le l \leq 2) Al​(0≤k≤l≤2)，则 A k ∪ A l = A A_k \cup A_l = A Ak​∪Al​=A。由鸽巢原理的一般形式， A k A_k Ak​和 A l A_l Al​中必有一个集合，其元素个数不少于 ⌈ 5 2 ⌉ = 3 \lceil \frac{5}{2}\rceil=3 ⌈25​⌉=3。显然该集合中的任意3个整数和能被3整除。

    5. 鸽巢原理应用

    5.1 完全图 K n K_n Kn​的边着色

    设给出的平面上的 n ( n ≥ 2 ) n(n \geq2) n(n≥2)个相异点，用线段将任意两个点都连接起来，所得的图形记为 K n K_n Kn​， K n K_n Kn​称为 n n n阶完全图，所给的 n n n个相异点都称为 K n K_n Kn​的顶点，连接 K n K_n Kn​任意两个顶点的线段称为 K n K_n Kn​的边。显然， K n K_n Kn​共有 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)​条边。

    定理：2-着色 K 6 K_6 K6​必含有一个单色三角形
    证明 设2-着色 K 6 K_6 K6​的个顶点为 A 1 , A 2 , … , A 6 A_1,A_2,\dots,A_6 A1​,A2​,…,A6​。由鸽巢原理，以 A 1 A_1 A1​为一个端点的5条边中必有3条边同色，不妨设 A 1 A 2 , A 1 A 3 , A 1 A 4 A_1A_2,A_1A_3,A_1A_4 A1​A2​,A1​A3​,A1​A4​是红边。如果三角形 A 2 A 3 A 4 A_2 A_3A_4 A2​A3​A4​是蓝色三角形，结论成立；否则三角形 A 2 A 3 A 4 A_2A_3A_4 A2​A3​A4​中至少有一条红边，设 A i A j ( 2 ≤ i < j ≤ 4 ) A_iA_j(2 \leq i < j \leq 4) Ai​Aj​(2≤i<j≤4)是红边，则三角形 A 1 A i A j A_1A_iA_j A1​Ai​Aj​是红色三角形。
    推论：任意6个人中必有3个人相互认识或者3个人相互不认识
    证明 用平面上的6个点代表这6个人，如果两个人认识则用红线把这两个点连接起来；如果两个人不认识则用蓝线把这两个点连接起来，这样得到一个2-着色 K 6 K_6 K6​问题，由定理1可以说明该推论是正确的。

    5.2 Ramsey数

    假设 a , b a, b a,b 为正整数， a , b ≥ 2 a, b \geq2 a,b≥2 , 则存在最小正整数 R ( a , b ) R(a, b ) R(a,b)人,使得有 a a a人相互认识,或者有 b b b人相互不认识, 称 R ( a , b ) R(a, b) R(a,b)为Ramsey数 (拉姆齐数)。也就是 R ( a , b ) R(a,b) R(a,b)个顶点的完全子图，用红蓝两种颜色进行着色，无论任何情况至少存在 （1）一个 a a a个顶点着红颜色的完全子图，或一个 b b b个顶点着蓝颜色的完全子图； （2）至少存在一个 a a a个顶点着蓝颜色的完全子图，或一个 b b b个顶点着红颜色的完全子图； 两者必有一个成立。

    定理1： R ( a , b ) = R ( b , a ) , R ( a , 2 ) = a R(a,b)=R(b,a),R(a,2) = a R(a,b)=R(b,a),R(a,2)=a定理2：对于任意整数 a , b ≥ 2 a,b \geq 2 a,b≥2， R ( a , b ) R(a,b) R(a,b)存在定理3： R ( a , b ) ⩽ R ( a − 1 , b ) + R ( a , b − 1 ) R(a, b) \leqslant R(a-1, b)+R(a, b-1) R(a,b)⩽R(a−1,b)+R(a,b−1)定理4：对于 a , b ≥ 2 a,b \geq 2 a,b≥2，有 R ( a , b ) ⩽ ( a + b − 2 a − 1 ) R(a, b) \leqslant \left( \begin{array}{c}{a+b-2} \\ {a-1}\end{array}\right) R(a,b)⩽(a+b−2a−1​)
    最新回复(0)