第3章 鸽巢原理2

Source

3.2 鸽巢原理加强形式

定理: q 1 , q 2 , . . . , q n q_1, q_2, ..., q_n q1,q2,...,qn为正整数,若将 q 1 + q 2 + . . . + q n − n + 1 q_1+ q_2+ ... + q_n - n + 1 q1+q2+...+qnn+1个物体被放进n个盒子内,那么

或者第1个盒子至少含有 q 1 q_1 q1个物体,或者第2个盒子至少含有 q 2 q_2 q2个物体,…,或者第n个盒子至少含有 q n q_n qn个物体

证: ( q 1 − 1 ) + ( q 2 − 1 ) + . . . + ( q n − 1 ) = q 1 + q 2 + . . . + q n − n (q_1-1) + (q_2 - 1) + ... + (q_n - 1) = q_1 + q_2 + ... + q_n -n (q11)+(q21)+...+(qn1)=q1+q2+...+qnn

鸽巢原理加强形式计数问题

【例】:一篮水果装有苹果、梨、桔子。为了保证或者至少8个苹果,或者至少6个梨或者至少9个桔子,则放入篮子中的水果的最少件数是多少?

( 8 + 6 + 9 ) − 3 + 1 = 21 (8+6+9)-3+1 = 21 (8+6+9)3+1=21

【推论】:设n和r都是正整数,如果n(r-1)+1个物体放入n个盒子,则至少有一个盒子含有r个或更多物体

平均原理: 如果n个非负整数 m 1 , m 2 , . . . , m n m_1, m_2, ..., m_n m1,m2,...,mn的平均数大于r-1,即 ( m 1 + m 2 + . . . + m n ) / n > r − 1 (m_1 + m_2 + ... + m_n) / n > r-1 (m1+m2+...+mn)/n>r1,则至少有一个整数大于或等于r

平均原理计数问题

【例】:100个人至少有多少人生在同一个月? ⌈ 100 12 ⌉ = 9 \lceil \frac{100}{12} \rceil = 9 12100=9

【例】:52张牌随机选26张,至少几张牌同一花色? ⌈ 26 4 ⌉ = 7 \lceil \frac{26}{4} \rceil = 7 426=7

【例】:52张牌选出7张相同花色,必须至少选出多少张牌? 6 ∗ 4 + 1 = 25 6 * 4 + 1 = 25 64+1=25

平均原理证明问题

【例】:证明从任意给出的5个正整数中必能选出3个数,它们的和能被3整除

证:任意正整数除以3的余数只能为0,1,2.设A为任意给出的5个正整数的集合,A中3个数和可以被3整除,只有一下4种情况。全0,全1,全2,012

t 0 , t 1 , t 2 t_0, t_1, t_2 t0,t1,t2为A中除以3余数分别为0,1,2的数的个数。

(1)若 t 0 , t 1 , t 2 t_0, t_1, t_2 t0,t1,t2均不为0,则一定有三个数除以3的余数分别为0,1,2

(2)若 t 0 , t 1 , t 2 t_0, t_1, t_2 t0,t1,t2中至少有一个为0,不妨设 t 0 = 0 t_0 = 0 t0=0,则 t 1 + t 2 = 5 t_1 + t_2 = 5 t1+t2=5.由平均原理知,至少有 ⌈ 5 2 ⌉ = 3 \lceil \frac{5}{2} \rceil = 3 25=3个数除以3的余数相同

【例】:在边长为1的正方形内取9个点,证明以这些点为顶点的各个三角形中,至少有一个三角形面积不大于 1 8 \frac{1}{8} 81

思路:抽屉有4个,点有9个,必有3个点在同一个区域内

证:将正方形分成4个边长为 1 2 \frac{1}{2} 21的小正方形,则至少有 ⌈ 9 4 ⌉ = 3 \lceil \frac{9}{4} \rceil = 3 49=3点落在同一个小正方形中,以这三点为面积不大于 1 3 \frac{1}{3} 31

【例】:两个大小不一的碟子,均被分成200个相等的扇形。在大碟子中任选100个扇形涂成红色,其余涂成蓝色。小蝶子中每一个扇形随机地涂成蓝色或者红色,数目无限制。将小碟子和大碟子中心重合。证能通过适合旋转,存在两个碟子相同颜色重合的扇形数至少是100个的情形。

思路:大碟子不动,转动小碟子,转完一个圈,回到原位,每个扇形匹配颜色次数均为100

当配色确定时,通过旋转小蝶,共有200种可能的对应方式,因此平均颜色重合数为20000/200=100

由鸽巢原理加强形式,肯定存在一种方式,其颜色重合数至少为100
【扩】:设 A = a 1 a 2 . . . a 20 A = a_1 a_2 ... a_{20} A=a1a2...a20是10个0和10个1组成的20位2进制数, B = b 1 b 2 . . . b 20 B = b_1 b_2 ... b_{20} B=b1b2...b20是任意的20位2进制数。令 C = b 1 b 2 . . . b 20 b 1 b 2 . . . b 20 = c 1 c 2 . . . c 40 C = b_1 b_2 ... b_{20} b_1 b_2 ... b_{20} = c_1 c_2 ... c_{40} C=b1b2...b20b1b2...b20=c1c2...c40则存在某个i, 1 ≤ i ≤ 21 1\le i \le 21 1i21,使得 c i c i + 1 . . . c i + 19 c_i c_{i+1} ... c_{i+19} cici+1...ci+19 a 1 a 2 . . . a 20 a_1 a_2 ... a_{20} a1a2...a20至少有10位对应数字相同

思路:体会一对 b i b i b_i b_i bibi的感觉,这不就是把一个环给拉开了吗

证:假象A从 c 1 c_1 c1开始一格一格移动,在移动到 c 21 c_{21} c21时,每对 b j b_j bj一共遍历所有 a 1 . . . a 20 a_1... a_{20} a1...a20。因为A中有10个0和10个1,每一对 b j b_j bj都有10位次对应相等。在20次的移动过程中,共有 10 ∗ 20 = 200 10*20=200 1020=200位次对应相等。因此必有一次移动,满足相同数字的格数至少是 200 20 = 10 \frac{200}{20}=10 20200=10

【本】:证明每个由 n 2 + 1 n^2+1 n2+1个是实数构成的序列,或者含有长度为 n + 1 n+1 n+1的递增子序列,或者含有长度为 n + 1 n+1 n+1的递减序列。

假设不存在长度为 n + 1 n+1 n+1的递增子序列,只需要构造一个长度为 n + 1 n+1 n+1的递减子序列。

m k m_k mk是以 a k a_k ak为起始的最长递增子序列长度, k = 1 , 2 , . . . , n 2 + 1 k = 1,2,..., n^2+1 k=1,2,...,n2+1,则对 ∀ k , 1 ≤ m k ≤ n \forall k, 1 \le m_k \le n k,1mkn,对 m 1 , m 2 , . . . , m n 2 + 1 m_1, m_2, ..., m_{n^2+1} m1,m2,...,mn2+1运用鸽巢原理加强形式,一定存在 ⌈ ( n 2 + 1 ) / n ⌉ = n + 1 \lceil (n^2+1)/ n \rceil = n+1 (n2+1)/n=n+1 m i m_i mi相等。

m k 1 = m k 2 = . . . = m k n + 1 m_{k_1} = m_{k_2} = ... = m_{k_{n+1}} mk1=mk2=...=mkn+1,其中 1 ≤ k 1 < k 2 < . . . < k n + 1 ≤ n 2 + 1 1\le k_1 \lt k_2 \lt ... \lt k_{n+1} \le n^2+1 1k1<k2<...<kn+1n2+1

假设存在 k i , k i + 1 k_i, k_{i+1} ki,ki+1,使得 a k i < a k i + 1 a_{k_i} < a_{k_{i+1}} aki<aki+1,把 a k i a_{k_i} aki加到以 a k i + 1 a_{k_{i+1}} aki+1 开始的最长递增子序列,则构成了以 a k i a_{k_i} aki开始的递增子序列,得 m k i > m k i + 1 m_{k_i} > m_{k_{i+1}} mki>mki+1,与 m k i = m k i + 1 m_{k_i} = m_{k_{i+1}} mki=mki+1矛盾

因此 a k 1 ≥ a k 2 ≥ . . . ≥ a k n + 1 a_{k_1} \ge a_{k_2} \ge ... \ge a_{k_{n+1}} ak1ak2...akn+1构成一条长度为 n + 1 n+1 n+1的递减序列

【扩】:将 n 2 + 1 n^2+1 n2+1个人并肩排成一条直线,是否一定能选出 n + 1 n+1 n+1个人向前迈一步,使得从左至右它们的身高是递增的或递减的

【例】:假设由15台工作站和10台服务器,可以用一条电缆直接把工作站连接到服务器,同一时刻只有一条到服务器的直接连接是有效的。如果项保证在任何时刻任何一组不超过10台工作站可以通过直接连接同时访问不同的服务器,所需的最少直接连接的数目是多少?

证:设工作站集合为{ w 1 , . . . , w 15 w_1, ..., w_{15} w1,...,w15},服务器集合为{ s 1 , . . . , s 10 s_1, ..., s_{10} s1,...,s10}

(1)当 i = 1 , . . . , 10 i = 1, ..., 10 i=1,...,10 w i w_i wi s i s_i si直接相连

(2)当 i = 11 , . . . . , 15 i = 11, ...., 15 i=11,....,15,把 w i w_i wi与所有服务器相连,

一共由60条直接连接。

下面这名60条是满足条件的最小直接连接数

假设直接连线数目只有59条,此时必有一个服务器最多连接5台工作站,否则直接连线数目将超过59.那么剩下的9台服务器和10台工作站无法满足工作站通过直接连接同时访问不同的服务器。

【例】:一个圆周被分成36段,在36段上按任意方式分配数字 1 , 2 , . . . , 36 1,2,...,36 1,2,...,36,证明存在三个相邻段,使得分配给他们的数字之和至少是56

证:记每段编号为 a 1 , a 2 , . . . , a 36 a_1, a_2, ..., a_{36} a1,a2,...,a36所有三个相邻段 ∑ ( a i − 1 + a i + a i + 1 ) = 3 ( 1 + 36 ) 36 2 \sum (a_{i-1}+a_{i}+a_{i+1}) = 3 \frac{(1+36)36}{2} (ai1+ai+ai+1)=32(1+36)36

共有36个相邻段,由平均定理, ⌈ 55.5 ⌉ = 56 \lceil 55.5 \rceil = 56 55.5=56