《抽屉原理》教案

  • 手机网页: 浏览手机版
  • 资源类别: 人教课标版 / 高中教案 / 高中竞赛教案
  • 文件类型: doc
  • 资源大小: 15 KB
  • 资源评级:
  • 更新时间: 2011/1/30 16:29:11
  • 资源来源: 会员转发
  • 资源提供: renheren [资源集]
  • 下载情况: 本月:获取中 总计:获取中
  • 下载点数: 获取中 下载点  如何增加下载点
  •  点此下载传统下载

资源简介:

约2250字。

  抽屉原理
  把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。
  抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
  形式一:
  证明:设把n+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个ai大于或等于2
  (用反证法)假设结论不成立,即对每一个ai都有ai<2,则因为ai是整数,应有ai≤1,于是有:
  a1+a2+…+an≤1+1+…+1=n<n+1
  这与题设矛盾。
  所以,至少有一个ai≥2,即必有一个集合中含有两个或两个以上的元素。
  形式二:
  设把n•m+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个ai大于或等于m+1。
  (用反证法)假设结论不成立,即对每一个ai都有ai<m+1,则因为ai是整数,应有ai≤m,于是有:
  a1+a2+…+an≤m+m+…+m=n•m
  n个m
  <n•m+1
  这与题设相矛盾。
  所以,至少有存在一个ai≥m+1
  高斯函数:
  对任意的实数x,
  [x]表示“不大于x的最大整数”.
  例如:[3.5]=3,[2.9]=2,
  [-2.5]=-3,[7]=7,……
  一般地,我们有:[x]≤x<[x]+1
  形式三:
  证明:设把n个元素分为k个集合A1,A2,…,Ak,用a1,a2,…,ak表示这k个集合里相应的元素个数,需要证明至少存在某个ai大于或等于[n/k]。
  (用反证法)假设结论不成立,即对每一个ai都有ai<[n/k],于是有:
  a1+a2+…+ak<[n/k]+[n/k]+…+[n/k]
  k个[n/k]
  =k•[n/k]≤k•(n/k)=n
  ∴ a1+a2+…+ak<n
  这与题设相矛盾。
  所以,必有一个集合中元素个数大于或等于[n/k]
  形式四:
  证明:设把q1+q2+…+qn-n+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个i,使得ai大于或等于qi。
  (用反证法)假设结论不成立,即对每一个ai都有ai<qi,因为ai为整数,应有ai≤qi-1,于是有:
  a1+a2+…+an≤q1+q2+…+qn-n
  <q1+q2+…+qn-n+1
  这与题设矛盾。
  所以,假设不成立,故必有一个i,在第i个集合中元素个数ai≥qi
  形式五:
  证明:(用反证法)将无穷多个元素分为有限个集合,假设这有限个集合中的元素的个数都是有限个,则有限个有限数相加,所得的数必是有限数,这就与题设产生矛盾,所以,假设不成立,故必有一个集合含有无穷多个元素。
  例题1:400人中至少有两个人的生日相同.
  分析:生日从1月1日排到12月31日,共有366个不相同的生日,我们把366个不同的生日看作366个抽屉,400人视为400个苹果,由表现形式1可知,至少有两人在同一个抽屉里,所以这400人中有两人的生日相同.
  解:将一年中的366天视为366个抽屉,400个人看作400个苹果,由抽屉原理的表现形式1可以得知:至少有两人的生日相同.
  例题2:边长为1的正方形中,任意放入9个点,求证这9个点中任取3个点组成的三角形中,至少有一个的面积不超过1/8.
  解:将边长为1的正方形等分成边长为 的四个小正方形,视这四个正方形为抽屉,9个点任意放入这四个正方形中,据形式2,必有三点落入同一个正方形内.现特别取出这个正方形来加以讨论.

 点此下载传统下载搜索更多相关资源
  • 说明:“点此下载”为无刷新无重复下载提示方式;“传统下载”为打开新页面进行下载,有重复下载提示。
  • 提示:非零点资源点击后将会扣点,不确认下载请勿点击。
  • 我要评价有奖报错加入收藏下载帮助

下载说明:

  • 没有确认下载前请不要点击“点此下载”、“传统下载”,点击后将会启动下载程序并扣除相应点数。
  • 如果资源不能正常使用或下载请点击有奖报错,报错证实将补点并奖励!
  • 为确保所下资源能正常使用,请使用[WinRAR v3.8]或以上版本解压本站资源。
  • 站内部分资源并非原创,若无意中侵犯到您的权利,敬请来信联系我们。

资源评论

共有 0位用户发表了评论 查看完整内容我要评价此资源