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

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

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

习题五(抽屉原理)

1.证明:在边长为2的等边三角形中任取5点,至少有两个点相距不超过1。 证明:如图所示,将正三角形分成4个边长为1的小等

边三角形,现在取5点,有4个小等边三角形,

根据抽屉原理,则至少有两点落在同一个小

等边三角形中,其距离不超过1。

2.在一个边长为1的正方形内任取9个点,证明以这些点为顶点的各个三角形中,至少有一个三角形的面积不大于8。

证明:如图所示,将正方形分为4个边长为2的小正方形,

现取9个点,则至少有三个点落在同一个小正方形

中,以这三点为顶点的三角形的面积不大于

2 长 高 2121。1 8

3.把从1到326的326个正整数任意分成5组,试证明其中必有1组,该组中

至少有一个数是同组中某两个数之和,或是同组中某个数的两倍。

证明:用反证法。

设任何一组中的每一个数,它既不等于同组中另外两数之和,也不等于同组中另一数的两倍。即任何一组数中任意两个数之差总不在该组中。

(1)由抽屉原理知,五组中必有一组其中至少有66个数,设为A组。

从中取66个数,记为a1,a2, ,a66,不妨设a66最大,

令 ai(1) a66 ai,i 1,2, ,65,显然1 ai(1) 326,

由假设知 ai(1) A,故这65个数必在另外四组B、C、D、E中。

(2)由抽屉原理知,B、C、D、E四组中必有一组至少含有17个ai(1),

设为B组,从中取17个ai(1),记为b1,b2, ,b17,同理不妨设b17最大,

令 bi(1) b17 bi i 1,2, ,16,显然1 bi(1) 326,且由假设知,bi(1) B, 又 bi(1) b17 bi (a66 aj) (a66 ak) ak aj A,

所以这16个数bi(1)必在C、D、E中。

(3)由抽屉原理知,C、D、E三组中必有一组至少含有6个bi(1),设为C组,

从中取6个bi(1),记为c1,c2, ,c6,同理不妨设c6最大,

令 ci(1) c6 ci,i 1,2, ,5,显然1 ci(1) 326,且由假设知ci(1) C, 又 ci(1) c(1b7 b) (1b7 kb) kb jb

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

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

B6 ci j

第1页

你可能喜欢

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

热门文档

相关文档

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