手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

第3章 鸽巢原理2

时间:2021/6/8 10:05:57|来源:|点击: 次

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

Copyright © 2002-2019 某某自媒体运营 版权所有