文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 组合数学(西安电子科技大学(第二版))习题5
侵权投诉

组合数学(西安电子科技大学(第二版))习题5

组合数学 姜建国 岳建国 西安电子科技大学(第二版) 习题参考答案

ci(1) bk bj (a66 an) (a66 am) am an A

所以这五个数必在D、E组中。

(4)由抽屉原理知,D、E两组中必有一组至少含有3个ci(1),设为D组,

从中取3个ci(1),记为d1,d2,d3,同理不妨设d3最大,

令di(1) d3 di,i 1,2,显然1 di(1) 326,且由假设知di(1) D, 同理可得di(1) A,B,C,故di(1) E。

(1)(1) (5)不妨设d1(1) d2,令 e d1(1) d2,则1 e 326,且由假设知e E,

同理可知,e A,B,C,D,

即e不在A、B、C、D、E任一组中,又1 e 326,与题设矛盾。 所以,命题成立。证毕。

4.任意一个由数字1,2,3组成的30位数,从中任意截取相邻的三位,证明在

各种不同位置的截取中,至少有两个三位数是相同的。数的位数30还可以再减少吗?为什么?

解:设由数字1,2,3组成的30位数为:a1a2 a30,

则任意截取相邻的三位,可能的截法有28种:

a1a2a3,a2a3a4, ,a27a28a29,a28a29a30,

而由1,2,3组成的三位数最多有33 27个,

则根据抽屉原理,这28个数中必至少有2个是相同的。

由证明过程可以知道,数的位数30不可以再减少了。

因为若改为29个,则可得到27个三位数,就不能保证有2个是相同的。 若改为截取相邻的5位,首先可知元素1、2、3的5-可重排列共有35 243

个。其次,由问题的性质可知至少要能截取出不同的244段才能保证结论成立,从而知该数至少应该有248位。

问题的一般描述是:任意一个由数字1,2,…,m组成的n=mk k位数,

从中任意截取相邻的k位,则在各种不同位置的截取中,至少有两个k位数是相同的。若希望至少有r个k位数是相同的,则应有n= r 1 mk k。

5.任取11个整数,求证其中至少有两个数的差是10的倍数。

证明:设这11个整数为:ai(i 1,2, ,11),不妨设a1 a2 a11,

令ri aimod10,则0 ri 10,

由抽屉原理知,必存在i,j,i j,使得ri rj,

则 10|(aj ai)。证毕。

问题的一般描述:任取n+1个整数,其中至少存在两数,其差是n的倍数。

上一页第2页

你可能喜欢

  • 组合数学容斥原理
  • 组合数学课件
  • 硕士英语综合教程
  • 数学分析选论
  • 数学分析试题及答案
  • 人工智能期末
  • 生成函数
  • 组合数学试卷

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email