下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1/1组合数学鸽巢原理例题-初中教育
组合数学鸽巢原理例题
鸽巢原理例题
组合数学鸽巢原理例题
证明[1,2n]中任意n+1个不同的数中至少有一对数互质设这n+1数为a1a2…an+1,令bi=ai+1(i=1,2,…,n)。明显,b1b2…bn=2n,a1,…,an+1,b1,…,bn这2n+1个数中必有二数相等,即存在bi与ai+1相等,而bi=ai+1,而ai与ai+1(即ai+1)是互质的。
组合数学鸽巢原理例题
一人以11周时间预备考试,他打算每天至少做一道题,但每周不多于12题。证明:存在连续的若干天,在这些天时他恰好做了21题。改为更少的题数如何?改为22题如何?令ai表示从第一天到第i天所做的题数之和。由于每天至少做一题,有:a1a2…a77=12*11=132。考虑序列:a1+21,a2+21,…,a77+21(=153).两个序列共有154个数,而ai≠aj(当i≠j时),同理,ai+21≠aj+21(当i≠j时),所以,必有某个aj=ai+21,即从第i+1天到第j天共做了21题。原命题改为小于21题,明显是成立的。
组合数学鸽巢原理例题
续:22题的状况若存在某一周没有做满12题,则a77+22154,使得这154个数最多到153,从而仍有aj=ai+22;若每周都做满12题,那么a1,a2,…,a77,a1+22,a2+22,…,a77+22这154个数恰在1~154之间。
若不存在i,j使得aj=ai+22,则它们取值遍历1,2,…,154。即有a1=1,a2=2,…,a22=22。那么,他在第一周里只做了7题,与每周做满12题假设冲突。所以,存在连续的若干天,他恰好做了22题。
组合数学鸽巢原理例题
设a1,a2,…,an是1,…,n的一个排列,证明,当n是奇数时,(a1-1)(a2-2)…(an-n)是一偶数。证明:只须证明上述因子中有一个是偶数即可。由于只要有一个因子是偶数,则积必为偶数。n是奇数时,1~n中有(n+1)/2个奇数,(n-1)/2个偶数。从而,a1,a3,…,an中至少有一个是奇数,设为a2i+1这样以来,(a2i+1-(2i+1))为偶数。乘积为偶数。证毕。
组合数学鸽巢原理例题
证明:在1~200中可选取100个数它们中任何两个数互素。并证明所选的100个数中的最小数不小于16。明显,当选出的数为101时,可用鸽巢原理证明,必存在两个数是倍数(或整除)关系。本题证明参见《辅导》P301,7.7题
组合数学鸽巢原理例题
证明:任给m个正整数a1,a2,…,am,必存在连续的若干项,其和是m的倍数(能被m整除)。证明:构造数列:S1=a1,S2=a1+a2,…,Sn=a1+a2+…+an;若某个Si已经可被m整除,则得证。设不存在被整除的状况,则每个Si模m的余数ri满意:1≤ri≤m-1。这样的ri共有m个。依据鸽巢原理,存在ij,但ri=rj。即Si与Sj同余。从而有:Sj-Si=km=ai+1+ai+2+…+aj.得证。
组合数学鸽巢原理例题
思索题1.2.一个1*1的方格里任选5个点,则必存在两点,其距离√2/2.空间直角坐标系中,我们把(x,y,z)坐标均为整数的点简称为格点,证明,任意9个格点中,必存在两点,其连线的中点亦是格点。设西工大在北京的办事处有90间房间。每次总是有100人中的90人到那里出差,试设计一
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 华师大版初中科学6.1信息的传递和通信
- 天弘爱理财APP整合方案
- 外勤医疗服务管理制度
- 异常情况和事故处理管理制度
- 表格制作方法
- 1《古诗三首》核心素养分层学习任务单-2022-2023学年三年级语文下册新课标(部编版)
- 2024年合作办理客运从业资格证理论考试题
- 2024年北京汽车客运资格证考试题目
- 2024年宣城客运从业资格证报名考试题目
- 2024年本溪客运从业资格证模拟考试练习题
- 部编版五年级语文上册《快乐读书吧》优秀课件
- 初中数学规律探索公开课完整教学课件
- 小学综合实践活动课课程标准
- 国家开放大学《现代汉语专题》章节自测参考答案
- 高三体育与健康教案
- 2022-2023学年天津市河西区高一年级上册学期期中数学试题【含答案】
- 国家开放大学《终身学习与职业发展》形考任务参考答案
- 山东省潍坊市2022-2023学年高二上学期期中考试语文试题 word版含答案
- 备用金申请单(完美版)
- SC200200施工升降机拆除施工方案
- 混凝土强度回弹检查表
评论
0/150
提交评论