压轴题 06 计数原理、二项式定理、概率统计压轴题六大题型汇总
本专题考查类型主要涉及点为计数原理、二项式定理、概率统计相关的知识点。
命题预测
预计2024年后命题会继续在上述几个方面进行。
题型01概率与数列结合问题 题型04概率统计与导数结合问题
高频考法 题型02二项式定理相关问题 题型05进制问题
题型03排列组合新定义问题 题型06条件概率全概率问题
01概率与数列结合问题
递推数列与概率知识的交汇问题,解决该类问题应该注意的事项有:
(1)做好互斥事件的划分,正确进行独立事件概率的计算;
(2)借助待定系数方法建立不同事件概率间的递推关系,即构建递推数列;
(3)正确运用数列求通项公式或求和的方法解决问题.
1.(21-22高二下·黑龙江双鸭山·期中)足球运动被誉为“世界第一运动”.深受青少年的喜爱.为推广足
球运动,某学校成立了足球社团,社团中的甲、乙、丙三名成员将进行传球训练,从甲开始随机地球传给
其他两人中的任意一人,接球者再随机地将球传给其他两人中的任意一人,如此不停地传下去,且假定每
次传球都能被接到.记开始传球的人为第1次触球者,第n次触球者是甲的概率为P ,即P =1.则下列说
n 1
法正确的个数是( )
1 1 1
(1)P =0;(2)P = ;(3)P =- P + ;(4)P <P .
2 3 2 n 2 n-1 2 9 10
A.1个 B.2个 C.3个 D.4个
2. (23-24高三下·山东菏泽·开学考试)国际象棋是国际通行的智力竞技运动.国际象棋使用8×8格黑白方
格相间棋盘,骨牌为每格与棋盘的方格大小相同的1×2格灰色方格.若某种黑白相间棋盘与骨牌满足以下三
点:①每块骨牌覆盖棋盘的相邻两格;②棋盘上每一格都被骨牌覆盖;③没有两块骨牌覆盖同一格,则称
骨牌构成了棋盘的一种完全覆盖.显然,我们能够举例说明8×8格黑白方格相间棋盘能被骨牌完全覆盖.
(1)证明:切掉8×8格黑白方格相间棋盘的对角两格,余下棋盘不能被骨牌完全覆盖;
(2)请你切掉8×8格的黑白方格相间棋盘的任意两个异色方格,然后画出余下棋盘的一种骨牌完全覆盖方式,并证明:无论切掉的是哪两个异色方格,余下棋盘都能被骨牌完全覆盖;
(3)记m×n格黑白方格相间棋盘的骨牌完全覆盖方式数为F(m,n),数列{F(2,n)}的前n项和为S ,证明:
n
S =F(2,n+2)-2.
n
3. (2024·江苏常州·模拟预测)某游戏设置了两套规则,规则A:抛掷一颗骰子n次,若n次结果向上的
点数之和大于2n时,继续下一次抛掷,否则停止抛掷;规则B:抛掷一颗骰子一次,结果向上的点数大于
2时,继续下一次抛掷,否则停止抛掷.
(1)若执行规则A,求抛掷次数恰为1次的概率;
(2)若执行规则B,证明:抛掷次数的数学期望不大于3.
4. (2024·浙江金华·模拟预测)现有n枚硬币C ,C ,⋯,C .对于每个k(k=1,2,⋯,n),硬币C 是有偏
1 2 n k
1
向的,即向上抛出后,它落下时正面朝上的概率为 .
2k+1
(1)将C ,C ,C 这3枚硬币抛起,设落下时正面朝上的硬币个数为X,求X的分布列及数学期望E(X);
1 2 3
(2)将这n枚硬币抛起,求落下时正面朝上的硬币个数为奇数的概率.
5. (2023·河南开封·一模)某市每年上半年都会举办“清明文化节”,下半年都会举办“菊花文化节”,
吸引着众多海内外游客.为了更好地配置“文化节”旅游相关资源,2023年该市旅游管理部门对初次参加
2
“菊花文化节”的游客进行了问卷调查,据统计,有 的人计划只参加“菊花文化节”,其他人还想参加
3
2024年的“清明文化节”,只参加“菊花文化节”的游客记1分,两个文化节都参加的游客记2分.假设
每位初次参加“菊花文化节”的游客计划是否来年参加“清明文化节”相互独立,将频率视为概率.
(1)从2023年初次参加“菊花文化节”的游客中随机抽取三人,求三人合计得分的数学期望;
(2)2024年的“清明文化节”拟定于4月4日至4月19日举行,为了吸引游客再次到访,该市计划免费向
到访的游客提供“单车自由行”和“观光电车行”两种出行服务.已知游客甲每天的出行将会在该市提供的
4
这两种出行服务中选择,甲第一天选择“单车自由行”的概率为 ,若前一天选择“单车自由行”,后一
5
1
天继续选择“单车自由行”的概率为 ,若前一天选择“观光电车行”,后一天继续选择“观光电车行”
4
1
的概率为 ,如此往复.
3
(i)求甲第二天选择“单车自由行”的概率;
(ii)求甲第n(n=1,2,⋯,16)天选择“单车自由行”的概率P ,并帮甲确定在2024年“清明文化
n
节”的16天中选择“单车自由行”的概率大于“观光电车行”的概率的天数.
02二项式定理相关问题
b
6.(2018·上海·一模)已知(1+2x) 6展开式的二项式系数的最大值为a,系数的最大值为b,则 =
a
.
7. ( 2024· 浙 江 · 模 拟 预 测 ) 已 知 . 若
(ax-1) 2 (2x-1) 3=a +a x+a x2+a x3+a x4+a x5
0 1 2 3 4 5
a +a +a +a +a +a =0,则a = .
0 1 2 3 4 5 3
8.(多选)(2024·全国·模拟预测)已知 , , , , , ,记
m∈N m≥2 a a ⋯ a ∈{0,1,2,⋯,9}
1 2 m
m
M=10m+∑10i-1a .当 a , a , ⋯ , a ,中含 k(k∈N,k≤m) 个6时,所有 M 不同值的个数记为 G(k) .
i 1 2 m
i=1
下列说法正确的有( )A.若m=2,则G(0)=81
B.若m=19,则G(k)>G(k+1)(k∈N,k≤18)
C.对于任意奇数
m,G(1)+G(3)+⋅⋅⋅+G(m)<5×10m-1
D.对于任意整数
m,G(1)+2G(2)+⋅⋅⋅+mG(m)=9m×10m-1
9.(2023·广西南宁·二模)已知当 x∈ ( - 1 , 1)时,有 1 =1-2x+4x2-…+(-2x) n+… ,若对任
2 2 1+2x
意的 x∈ ( - 1 , 1)都有 x =a +a x+…+a xn+… ,则 a = .
2 2 (1-x3)(1+2x) 0 1 n 9
10.(2024·湖南衡阳·二模)莫比乌斯函数在数论中有着广泛的应用.所有大于1的正整数n都可以被唯
一 表 示 为 有 限 个 质 数 的 乘 积 形 式 : ( 为 的 质 因 数 个 数 , 为 质 数 ,
n=pr 1pr 2⋅⋅⋅pr k k n p
1 2 k i
r ≥1,i=1,2,⋅⋅⋅,k),例如:90=2×32×5,对应k=3,p =2,p =3,p =5,r =1,r =2,r =1.现对
i 1 2 3 1 2 3
任意n∈N* ,定义莫比乌斯函数μ(n)=¿
(1)求μ(78),μ(375);
(2)若正整数x,y互质,证明:μ(xy)=μ(x)μ(y);
(3)若n>1且μ(n)=1,记n的所有真因数(除了 1 和n以外的因数)依次为a ,a ,⋅⋅⋅,a ,证明:
1 2 m
.
μ(a )+μ(a )+⋅⋅⋅+μ(a )=-2
1 2 m
03排列组合新定义问题
11.(23-24高三下·江苏泰州·阶段练习)将“用一条线段联结两个点”称为一次操作,把操作得到的线段
称为“边”.若单位圆上n个颜色不相同且位置固定的点经过k次操作后,从任意一点出发,沿着边可以到
达其他任意点,就称这n个点和k条边所构成的图形满足“条件T”,并将所有满足“条件T”的图形个
数记为T(n,k),则T(5,4)= .
12. (22-23高三下·浙江杭州·阶段练习)七选五型选择题组是许多类型考试的热门题型.为研究此类题型
的选拔能力,建立以下模型.有数组a ,a ,…,a和数组b ,b ,…,b ,规定a (1≤ j≤i+2)与b 相配对则
1 2 i 1 2 i+2 j j
视为“正确配对”,反之皆为“错误配对”.设P(n)为i=n时,对于任意j(1≤ j≤n)都不存在“正确配
对”的配对方式数,即错排方式数.
(1)请直接写出P(1),P(2)的值;
(2)已知P(n+1)=(n+2)P(n)+nP(n-1).
①对a ,a ,…,a 和b ,b ,…,b 进行随机配对,记X为“正确配对”的个数.请写出X的分布列并求E(X);
1 2 5 1 2 7
②试给出P(n+1)=(n+2)P(n)+nP(n-1)的证明.
13.(2024·辽宁·模拟预测)若集合A,B,C,D满足A,B,C都是D的子集,且A∩B,B∩C,A∩C均
只有一个元素,且A∩B∩C=∅,称(A,B,C)为D的一个“有序子集列”,若D有5个元素,则有多少
个“有序子集列” .
14.(2024·辽宁·一模)十七世纪至十八世纪的德国数学家莱布尼兹是世界上第一个提出二进制记数法的
人,用二进制记数只需数字0和1,对于整数可理解为逢二进一,例如:自然数1在二进制中就表示为 ,
(1)
2
2 表 示 为 , 3 表 示 为 , 5 表 示 为 , 发 现 若 可 表 示 为 二 进 制 表 达 式
(10) (11) (101) n∈N
2 2 2 +(a a a ⋅⋅⋅a a ) , 则 n=a ⋅2k+a ⋅2k-1+⋅⋅⋅+a ⋅21+a , 其 中 a =1 , a =0 或 1 (
0 1 2 k-1 k 2 0 1 k-1 k 0 i
i=1,2,⋅⋅⋅k).
(1)记 ,求证: ;
S(n)=a +a +⋅⋅⋅+a +a S(8n+3)=S(4n+3)
0 1 k-1 k
(2)记I(n)为整数n的二进制表达式中的0的个数,如I(2)=1,I(3)=0.
(ⅰ)求I(60);
511
(ⅱ)求 (用数字作答).
∑2I(n)
n=1
15.(2024·广东·模拟预测)在组合恒等式的证明中,构造一个具体的计数模型从而证明组合恒等式的方
法叫做组合分析法,该方法体现了数学的简洁美,我们将通过如下的例子感受其妙处所在.
(1)对于n元一次方程x +x +⋯+x =k,试求其正整数解的个数;
1 2 n
(2)对于n元一次方程组¿,试求其非负整数解的个数;
n
(3)证明: Cn =∑Ck Cn-k (可不使用组合分析法证明).
p+q+n+1 p+k q+n-k
k=0
注:¿与¿可视为二元一次方程的两组不同解.
04概率统计与导数结合问题
16.(2024·浙江杭州·二模)在概率统计中,常常用频率估计概率.已知袋中有若干个红球和白球,有放回
地随机摸球n次,红球出现m次.假设每次摸出红球的概率为p,根据频率估计概率的思想,则每次摸出红
m
球的概率p的估计值为^p= .
n
(1)若袋中这两种颜色球的个数之比为1:3,不知道哪种颜色的球多.有放回地随机摸取3个球,设摸出的
球为红球的次数为Y,则Y~B(3,p).
注: 表示当每次摸出红球的概率为 时,摸出红球次数为 的概率)
P (Y =k) p k
p
(ⅰ)完成下表;
k 0 1 2 3
P (Y =k) 27 1
1
4 64 64
P (Y =k) 9 27
3
4 64 64
(ⅱ)在统计理论中,把使得 的取值达到最大时的 ,作为 的估计值,记为 ,请写出 的值.
P (Y =k) p p ^p ^p
p
(2)把(1)中“使得 的取值达到最大时的 作为 的估计值 ”的思想称为最大似然原理.基于最
P (Y =k) p p ^p
p
大似然原理的最大似然参数估计方法称为最大似然估计.
具体步骤:先对参数 构建对数似然函数 ,再对其关于参数 求导,得到似然方程 ,最后求解参
θ l(θ) θ l'(θ)=0
n n
数 的估计值.已知 的参数 的对数似然函数为 ,其
θ Y~B(n,p) p l(p)=∑ X ln p+∑(1-X )ln(1-p)
i i
i=1 i=1中X =¿.求参数p的估计值,并且说明频率估计概率的合理性.
i
17.(2024·山东济南·二模)随机游走在空气中的烟雾扩散、股票市场的价格波动等动态随机现象中有重
要应用.在平面直角坐标系中,粒子从原点出发,每秒向左、向右、向上或向下移动一个单位,且向四个方
1
向移动的概率均为 .例如在1秒末,粒子会等可能地出现在(1,0),(-1,0),(0,1),(0,-1)四点处.
4
(1)设粒子在第2秒末移动到点(x,y),记x+ y的取值为随机变量X ,求X 的分布列和数学期望E(X);
(2)记第n秒末粒子回到原点的概率为p .
n
n
(i)已知 求 以及 ;
∑(Ck ) 2=Cn p ,p p
n 2n 3 4 2n
k=0
(ii)令 ,记 为数列 的前 项和,若对任意实数 ,存在 ,使得 ,则称粒子
b =p S {b } n M>0 n∈N* S >M
n 2n n n n
(n) n ( 6 ) 1 (n) n
是常返的.已知 √2πn <n!< 4√2πn ,证明:该粒子是常返的.
e π e
a(x-1)
18.(2024·重庆·模拟预测)函数f (x)=lnx- .
x+1
(1)讨论f (x)的单调性;
(2)若函数 f (x) 有两个极值点 x ,x ,曲线 y=f (x) 上两点 (x ,f (x )) , (x ,f (x )) 连线斜率记为k,求证:
1 2 1 1 2 2
2-a
k> ;
a-1
(3)盒子中有编号为1~100的100个小球(除编号外无区别),有放回的随机抽取 20个小球,记抽取的
1
20个小球编号各不相同的概率为p,求证:p<
.
e2
19.(2024·河北沧州·模拟预测)某景区的索道共有三种购票类型,分别为单程上山票、单程下山票、双
程上下山票.为提高服务水平,现对当日购票的120人征集意见,当日购买单程上山票、单程下山票和双
程票的人数分别为36、60和24.
(1)若按购票类型采用分层随机抽样的方法从这120人中随机抽取10人,再从这10人中随机抽取4人,
求随机抽取的4人中恰有2人购买单程上山票的概率.
(2)记单程下山票和双程票为回程票,若在征集意见时要求把购买单程上山票的 2人和购买回程票的m(
m>2且m∈N*
)人组成一组,负责人从某组中任选2人进行询问,若选出的2人的购票类型相同,则该
组标为A,否则该组标为B,记询问的某组被标为B的概率为p.
(i)试用含m的代数式表示p;
(ii)若一共询问了5组,用g(p)表示恰有3组被标为B的概率,试求g(p)的最大值及此时m的值.
20.(2024·广东汕头·一模)2023年11月,我国教育部发布了《中小学实验教学基本目录》,内容包括
高中数学在内共有16个学科900多项实验与实践活动.我市某学校的数学老师组织学生到“牛田洋”进行
科学实践活动,在某种植番石榴的果园中,老师建议学生尝试去摘全园最大的番石榴,规定只能摘一次,
并且只可以向前走,不能回头.结果,学生小明两手空空走出果园,因为他不知道前面是否有更大的,所以
没有摘,走到前面时,又发觉总不及之前见到的,最后什么也没摘到.假设小明在果园中一共会遇到n颗番
石榴(不妨设n颗番石榴的大小各不相同),最大的那颗番石榴出现在各个位置上的概率相等,为了尽可
能在这些番石榴中摘到那颗最大的,小明在老师的指导下采用了如下策略:不摘前k(1≤k<n)颗番石榴,
自第k+1颗开始,只要发现比他前面见过的番石榴大的,就摘这颗番石榴,否则就摘最后一颗.设k=tn,
记该学生摘到那颗最大番石榴的概率为P.
(1)若n=4,k=2,求P;(2)当n趋向于无穷大时,从理论的角度,求P的最大值及P取最大值时t的值.
1 1 1 n
(取 + +⋯+ =ln )
k k+1 n-1 k
05进制问题
21.(20-21高三下·江苏·阶段练习)十六进制是一种逢16进1的计数制.我国曾在重量单位上使用过十六进
制,比如成语“半斤八两”,即十六两为一斤.在现代,计算机中也常用到十六进制,其采用数字0∼9和
字母A∼F共16个计数符号.这些符号与十进制的数的对应关系如下表:
十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F
十进制 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
例如,用十六进制表示:E+D=1B,则A×B=( )
A.6E B.72 C.5F D.BD
22.(23-24高三下·江西赣州·期中)十进制计数法简单易懂,方便人们进行计算.也可以用其他进制表示
数,如十进制下,68=1×72+2×7+5,用七进制表示68这个数就是125,个位数为5,那么用七进制表
示十进制的611,其个位数是( )
A.1 B.2 C.5 D.6
23.(2022·江苏南京·三模)19世纪,美国天文学家西蒙·纽康在翻阅对数表时,偶然发现表中以 1开头
的数出现的频率更高.约半个世纪后,物理学家本福特又重新发现这个现象,从实际生活得出的大量数据
1
中,以1开头的数出现的频率约为总数的三成,接近期望值 的3倍,并提出本福特定律,即在大量b进
9
制随机数据中,以n开头的数出现的概率为 (n+1),如斐波那契数、阶乘数、素数等都比较
P (n)=log
b b n
符合该定律.后来常有数学爱好者用此定律来检验某些经济数据、选举数据等大数据的真实性.根据本福
9
特定律,在某项大量经济数据(十进制)中,以6开头的数出现的概率为 ;若 ,
∑ P (n)=P (1)
10 10
n=k
k∈N*,k≤9,则k的值为 .
24.(2014·吉林延边·一模)给出下列命题:
① 已知线性回归方程^y=3+2x,当变量x增加2个单位,其预报值平均增加4个单位;
② 在进制计算中, ;
100 =11
(2) (3)
③ 若 ,且 ,则 ;
ξ~N(3,σ2 ) P(0≤ξ≤3)=0.4 P(ξ≥6)=0.1
1
④ “ a=∫❑√1-x2dx ”是“函数 y=cos2 (ax)-sin2 (ax) 的最小正周期为4”的充要条件;
0
⑤ 设函数 f(x)= 2014x+1+2013 +2014sinx ( x∈ [ - π , π])的最大值为 M,最小值为 m,则 M+
2014x+1 2 2
m=4027,其中正确命题的个数是 个.
25.(2022·安徽合肥·二模)通信编码信号利用BEC信道传输,如图1,若BEC信道传输成功,则接收端收
到的信号与发来的信号完全相同;若BEC信道传输失败,则接收端收不到任何信号.传统通信传输技术采用
多个信道各自独立传输信号(以两个信道为例,如图2).华为公司5G信道编码采用土耳其通讯技术专家Erdal Arikan 教授的极化码技术(以两个相互独立的BEC
信道传输信号为例):如图3,信号U 直接从信道2传输;信号U 在传输前先与U “异或”运算得到信
2 1 2
号X ,再从信道1传输.接收端对收到的信号,运用“异或”运算性质进行解码,从而得到或得不到发送
1
的信号U 或U .
1 2
(注:“异或”是一种2进制数学逻辑运算.两个相同数字“异或”得到0,两个不同数字“异或”得到
1,“异或”运算用符号“⊕”表示:0⊕0=0,1⊕1=0,1⊕0=1,0⊕1=1.“异或”运算性质:
,则 ).假设每个信道传输成功的概率均为 . .
A⊕B=C A=C⊕B p(0<p<1) U ,U ={0,1}
1 2
(1)在传统传输方案中,设“信号U 和U 均被成功接收”为事件A,求P(A):
1 2
(2)对于极化码技术:①求信号U 被成功解码(即根据BEC信道1与2传输的信号可确定U 的值)的概率;
1 1
②若对输入信号U 赋值(如U =0)作为已知信号,接收端只解码信号U ,求信号U 被成功解码的概率.
1 1 2 2
06条件概率全概率问题
P(AB)
条件概率公式P(A|B)=
P(B)
26.(多选)(23-24高三下·江苏泰州·阶段练习)甲、乙两个口袋各装有1个红球和2个白球,这些球除
颜色外完全相同.把从甲、乙两个口袋中各任取一个球放入对方口袋中称为一次操作,重复 n次操作后,
甲口袋中恰有0个红球,1个红球,2个红球分别记为事件A ,B ,C ,则( )
n n n
5 4 2
A.P(B )= B.P(C |A )= C.P(B C )= D .
1 9 3 1 27 1 2 81
55
P(A +B )=
1 2 81
27. (2024·浙江宁波·二模)三个人利用手机软件依次进行拼手气抢红包活动,红包的总金额数为
3n(n≥2,n∈N)个单位.第一个人抢到的金额数为1到2n-1个单位且等可能(记第一个人抢完后剩余的
金额数为W),第二个人在剩余的W个金额数中抢到1到W -1个单位且等可能,第三个人抢到剩余的所
有金额数,并且每个人抢到的金额数均为整数个单位.三个人都抢完后,获得金额数最高的人称为手气王
(若有多人金额数相同且最高,则先抢到最高金额数的人称为手气王).
(1)若n=2,则第一个人抢到的金额数可能为1,2,3个单位且等可能.
(i)求第一个人抢到金额数X的分布列与期望;
(ii)求第一个人获得手气王的概率;(2)在三个人抢到的金额数为2,3,4的一个排列的条件下,求第一个人获得手气王的概率.
28.(2024·浙江杭州·模拟预测)小蒋同学喜欢吃饺子,某日他前往食堂购买 16个饺子,其中有X个为
1
香菇肉馅,其余为玉米肉馅,且P(X=i)= ,i=0,1,⋯,16.在小蒋吃到的前13个饺子均为玉米肉馅的
17
条件下,这16个饺子全部为玉米肉馅的概率为( )
4 13 14 5
A. B. C. D.
5 16 17 6
29.(多选)(2024·山西朔州·一模)在信道内传输M,N,P信号,信号的传输相互独立,发送某一信号
1-α
时,收到的信号字母不变的概率为α(0<α<1),收到其他两个信号的概率均为 .若输入四个相同的信
2
号MMMM,NNNN,PPPP的概率分别为p ,p ,p ,且p +p +p =1.记事件M ,N ,P 分别表示“输
1 2 3 1 2 3 1 1 1
入MMMM”“输入NNNN”“输入PPPP”,事件D表示“依次输出MNPM”,则( )
A.若输入信号 ,则输出的信号只有两个 的概率为
MMMM M α2(1-α) 2
B.P¿
C.P¿
D.P¿
30.(2024·辽宁·三模)一个书包中有标号为“1,1,2,2,3,3,⋯,n,n”的2n张卡片.一个人每次从中拿出
一张卡片,并且不放回;如果他拿出一张与已拿出的卡片中有相同标号的卡片,则他将两张卡片都扔掉;
如果他手中有3张单张卡片或者书包中卡片全部被拿走,则操作结束.记书包中卡片全部被拿走的概率为P ,
n
则P = .P = .
3 7
{ m }
31.(2024·浙江嘉兴·二模)已知集合 A= ∑2a i∣0≤a <a <⋯<a ,a∈N ,定义:当 m=t 时,把
1 2 m i
i=1
集合 中所有的数从小到大排列成数列 ,数列 的前 项和为 .例如: 时,
A {b(t) } {b(t) } n S(t) t=2
n n n
b(2) =20+21=3,b(2) =20+22=5,b(2) =21+22=6,b(2) =20+23=9,⋯ ,
1 2 3 4
S(2) =b(2) +b(2) +b(2) +b(2) =23.
4 1 2 3 4
(1)写出b(2) ,b(2) ,并求S(2) ;
5 6 10
(2)判断88是否为数列 中的项.若是,求出是第几项;若不是,请说明理由;
{b(3) }
n
(3)若2024是数列 中的某一项 ,求 及 的值.
{b(t) } b(t ) t ,n S(t )
n 0 n 0 0 0 n
0 0
32.(2024·浙江杭州·模拟预测)在概率较难计算但数据量相当大、误差允许的情况下,可以使用
UnionBound(布尔不等式)进行估计概率.已知UnionBound不等式为:记随机事件A ,⋯,A ,则
1 n
n
.其误差允许下可将左右两边视为近似相等.据此解决以下问题:
P(A ∪A ∪⋯∪A )≤∑❑P(A )
1 2 n i
i=1
(1)有n个不同的球,其中k个有数字标号.每次等概率随机抽取n个球中的一个球.抽完后放回.记抽取t次球后
k个有数字标号的球每个都至少抽了一次的概率为P(t),现在给定常数p,则满足P(t)≥p的t的最小值为多
少?请用UnionBound估计其近似的最小值,结果不用取整.这里n相当大且远大于k;(2)然而实际情况中,UnionBound精度往往不够,因此需要用容斥原理求出精确值.已知概率容斥原理:
n
记随机事件 A ,⋯,A ,则 P(A ∪A ∪⋯∪A )=∑(-1) k-1 ∑ ❑P(A A ⋯A ). .试问
1 n 1 2 n a a a
1 2 k
k=1 1≤a<a <⋯<a ≤n
1 2 k
在(1)的情况下,用容斥原理求出的精确的t的最小值是多少(结果不用取整)?n相当大且远大于k.
(1)(2)问参考数据:当 相当大时,取( 1) x 1.
x 1- =
x e
33.(2024·湖北·模拟预测)欧拉函数在密码学中有重要的应用.设 n 为正整数,集合
,欧拉函数 的值等于集合 中与n互质的正整数的个数;记 表示x除
X ={1,2,⋅⋅⋅,n-1} φ(n) X M(x,y)
n n
以y的余数(x和y均为正整数),
(1)求φ(6)和φ(15);
(2)现有三个素数p,q,e(p<q<e),n=pq,存在正整数d满足M(de,φ(n))=1;已知对素数a和
,均有 ,证明:若 ,则 ;
x∈X M(xa-1,a)=1 x∈X x=M([M(xc,n)] d,n)
a n
(3)设n为两个未知素数的乘积, , 为另两个更大的已知素数,且 ;又 ,
e e 2e =3e +1 c =M(xe 1,n)
1 2 1 2 1
c =M(xe 2,n) , x∈X ,试用 c , c 和n求出x的值.
2 n 1 2
34.(2024·海南海口·一模)在计算机科学中, 维数组 是一
n X=(x ,x ,⋯,x ),x∈{0,1},i∈N ,n≥2
1 2 n i +
种 基 础 而 重 要 的 数 据 结 构 , 它 在 各 种 编 程 语 言 中 被 广 泛 使 用 . 对 于 n维 数 组
A=(a ,a ,⋯,a ),B=(b ,b ,⋯,b ) ,定义 A 与 B 的差为 A-B=(|a -b |,|a -b |,⋯,|a -b |),A 与 B
1 2 n 1 2 n 1 1 2 2 n n
n
之间的距离为 .
d(A,B)=∑|a -b|
i i
i=1
(1)若n维数组C=(0,0,⋯,0),证明:d(A,C)+d(B,C)≥d(A,B);
(2)证明:对任意的数组A,B,C,有d(A-C,B-C)=d(A,B);
(3)设集合S =¿,若集合P中有m(m≥2)个n维数组,记P中所有两元素间的距离的平均值为d(P),证明:
n
mn
d(P)≤ .
2(m-1)
35.(2024·山西临汾·二模)在计算机科学中, 维数组 是一种基
n X=(x ,x ,⋯,x ),x∈{0,1},i∈N
1 2 n i +
础而重要的数据结构,它在各种编程语言中被广泛使用.对于 维数组 ,
n A=(a ,a ,⋯,a )
1 2 n
B=(b ,b ,⋯,b ) ,定义 A 与 B 的差为 A-B=(|a -b |,|a -b |,⋯,|a -b |),A 与 B 之间的距离为
1 2 n 1 1 2 2 n n
n
.
d(A,B)=∑|a -b|
i i
i=1
(1)若n维数组O=(0,0,⋯,0),证明:d(A,O)+d(B,O)≥d(A,B);
(2)证明:对任意的数组A,B,C,有d(A-C,B-C)=d(A,B);(3)设集合P中有m(m≥2)个n维数组,记P中所有两元素间的距离的平均值为d(P),证明:
mn
d(P)≤ .
2(m-1)