运用抽屉原理巧解组合问题

抽屉原理：把为数众多的物品放人不多的抽屉中,则至少有一个抽屉中放进了两个或更多个物品。 该原理指出的是一件简单明了的事实,其正确性也是显而 易见的。利用抽屉原理可以解决许多有趣的组合问题。 抽屉原理的数学表现形式： 定理：设个物品放人ｎ个盒子中,则至少存在,使得第ｉ个盒子内至少放有ｑｉ个物品。 证明：若对所有的,第ｉ个盒子中至多只有个物品,则ｎ个盒子中至多有品,与题设有品相矛盾故定理成立。 推论１：如果把ｎ＋１个物品放入ｎ个盒子中,那么至少有一个盒子中有两个或更多个物品。２即可） 推论２：若将ｍ个物品…     

错位数公式的化简

错位排列数把编号为1，2，…，n的n个球装入编号为1，2，…，n的n个盒子中，每个盒子装一个球，但1号盒子里不能装1号球，2号盒子里不能装2号球，…，n号盒子里不能装n号球，这种装球的方法就叫做1，2，…，n的错位排列，这种装球的方法数就叫做1，2，…，n的错位排列数，记作Dn．     

解题策略(六)

抽屉原理把3个桃子放入A、B两个抽屉,有以下四种不同的情况:从这四种情况可以看出:至少有一个抽屉里有2个桃子。其实,这里面包含着一个重要的数学原理——抽屉原理。如果把n+1个桃子放入n个抽屉中,那么必然有一个抽屉中至少有2个桃子(抽屉原理     

试谈“抽屉原则”

我们先看几个句子：将6个球放到5个抽屉中，不管如何放法至少有一个抽屉中的球数不少于2个。任运13人，至少有两个人出生的月份是相同的任选5个整数，用4除之，至少有两个数的除数（指在余数公式中定义的除数）是相同的。以上实例或概括成抽屉原则：将不少于m＋1个物体，随意放在m个抽屉中去，则至少有一个抽屉中的物体不少于2个。（注意在使用时，关键是设抽屉可代表物，数，任何一个东西，但必须是个整数）证明：（反证法）假定每个抽屉中的物体都少于2个，那么每个抽屉的物体就不会多于1个（有可能没有），那么它们中的物体个数之和也不…     

球·盒子模型的应用

在解决排列组合的问题时,常常碰到有关球放入盒子的问题,这类问题的变化较多,学生掌握起来比较困难,且其它一些问题可以转化为球·盒子问题,也即具有模型置换的功能,本文拟就此谈些方法.模型之一:把m个不同小球随意放入n个不同盒子.把m个不同小球随意放入n个不同盒子的问题,实质上是一个重复排列的问题,可以用乘法原理解决.第一个球有n种放法,第二个球有n种放法……第m个球有n种放法,故共有n·n……nm=nm种不同的放法.例1　五个学生报名参加数、理、化、外四门学科竞赛,每人限报一门,则报名方法有多少种?分析　五个学生类比于5个不同的小球,…     

浅谈“抽屉原则”及其应用

一、“抽屉原则”的基本知识抽屉原则是一个重要的组合学原则,又叫“鸽笼原则”,学名狄利克雷(Dirich-let、德国数学家)原则,大意是指一群鸽子飞进比鸽子数少的鸽笼里,可以断言至少有一只笼子里有不少于两只的鸽子。也可以描述为:若干本书放入比书本数少的抽屉中,那么至少有一个抽屉中有两本或更多本书。下面用数学语言来描绘抽屉原则。 1.抽屉原则的简单形式:把多于n个的元素按任一确定的方式分成几个集合,那么至少有一个集合中含有不少于两个的元素。用反证法证明:若分成的n个集体中,每个集合都不含有两个或两个以上元     

一道概率题的拓展与证明

问题1设有标号为1,2,3的三个盒子和标号为1,2,3的三个小球,将这三个小球任意地放入这三个盒子,每个盒子放一个小球.若j(j=1,2,3)号球放入j号盒子,则称该球放对     

解组合问题的一个重要模型

r 个无区别的小球分别放入 n 个不同的盒子中,每个盒子所放球数不加限制,其放法总数为:G_(n r-1)~r.在解一些组合问题时经常用到这一结论,我们可以把这个结论看成一个模型,即“球·盒子模型”,利用这个模型我们可以很方便地解决一些组合问题.首先证明这个结论.考察 n 1个1和个 r     

奇妙的“抽屉原理”

抽屉原理： （1）将n＋1件东西放在”个抽屉里,则至少有一个抽屉里至少有两件东西． （2）将m件东西放在n个抽屉里,当川一nq时,则至少有一个抽屉里至少有q件东西．     

数学趣味竞赛题(初一)

1.数2,4,6,8,…是连续偶数,若五个连续偶数的和为2000,则这五个数中最小的一个数是()。 A .392 B.394 C.396 2.如图,有两个各边完全相等的正方形和正五边形,若正五边形按逆时针方向开始旋转,而它上面的正方形按顺时针方向一边对着一边旋转,则直到正五边形的AE边和正方形的。边重合为止,正方形旋转的圈数为()。D .398 7.如图,在一个三角形中,10、11、12、13、14、15这六个数各自放置在一个圆圈内,使得三角形各边上的三个数之和S是相同的,这S的最大值可能是 8.某人将球放在两个盒子里,每只大盒子装12只,小盒子装5只,恰好装完。若球数为99…     

一道组合题及其变式的解析

变式训练和一题多解是提高思维能力的有效途径,尤其是对排列组合应用题,解答常常似是而非,而又难知错误所在,此时,利用变式及一题多解来比较、纠错尤显必要.请看下面一道典型习题.【例】将n 1个相同的小球装入n个不同的盒是,若不允许有空盒,有多少种不同的装法?解析一:问题可转化为将排成一排的n 1个球,分成n部分,每部分至少有一个球的分法数.n 1个球之间具有n个空档,设将n-1块隔板插入这n个空档中,每一种插法都可将n 1个球分成符合要求的n部分,所有的插法数为Cnn-1种,即有Cnn-1种装法.解法二:设n个小盒所装球个数分别为x1、x2…xn,则问题…     

抽屉原理与电脑算命

“电脑算命”看起来挺玄乎,只要你报出自己出生的年、月、日和性别,一按按键,屏幕上就会出现所谓性格、命运的句子,据说这就是你的“命”。其实这充其量不过是一种电脑游戏而已。我们用数学上的抽屉原理很容易说明它的荒谬。抽屉原理又称鸽笼原理或狄利克雷原理,它是数学中证明存在性的一种特殊方法。举个最简单的例子,把3个苹果按任意的方式放入两个抽屉中,那么一定有一个抽屉里放有两个或两个以上的苹果。这是因为如果每一个抽屉里最多能放一个苹果,那么两个抽屉里最多只能放两个苹果。运用同样的推理可以得到:原理1 把多于n个的物体放…     

抽屉原理

抽屉原理是组合数学中的一个重要原理,原理虽简单,但在数学中(特别是在解题时)经常用到,对一些看上去很复杂甚至无从下手的问题,应用抽屉原理,能使问题得到非常巧妙地解决.本文主要介绍抽屉原理在解题中的应用. 内容概述 在生活中,要把5个苹果放入4个抽屉中去,不论怎样放,都至少有一个抽屉中有2个或2个以上的苹果.更一般地说,只要被放置的苹果数多于抽屉数,就至少有一个抽屉中有2个或2个以上的苹果.这是一个简单的事实,而这个简单的事实中却包含着一个重要的原理——抽屉原理.     

巧用抽屉原理证明代数不等式

要把3个苹果放到2个抽屉里,无论怎样放,我们发现有一个抽屉里面至少有2个苹果.这一现象,就是人们所说的"抽屉原理".抽屉原理的一般含义为:"如果每个抽屉代表一个集合,一个苹果可以代表一个元素,假如把n+1或多于n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素."抽屉原理有时也被称为鸽笼原理.     

存在性智力趣题与抽屉原理

一本数学智力趣题集中有如下三道趣题.1.平面上有1987个点,若其中任何三点中都有两点的距离小于1,则必存在一个半径为1的圆,它至少盖住这1987个点中的994个点.2.一个正方形被9条直线分割,若其中每一条直线都与正方形的一对对边相交,且把该正方形分成面积比为2∶3的两个梯形,则这9条直线中至少有3条直线交于同一点.3.平面上有n(n≥4)个互不相同的点,每两点间用直线段相连,若其中长度为d的线段有n 1条,则这n个点中至少有1点,从该点出发的线段中至少有3条线段长度为d.上述三道趣题有一个共同点,它们都是与数量有关的存在性命题.关于涉及数量的存在性的证明,有一个简单而强有力的武器——抽屉原理:若将sn b个苹果(s,b,n∈N ,0     

排列组合中球与盒子模型的应用题

在解决排列组合问题时,常常会遇到有关球放入盒子的问题,这类问题的变化较多,学生掌握起来有一定困难,而且还有很多问题可转化为球与盒子的问题.本文就此谈几点模型的归纳及应用方法. 模型一:把m个不同小球随意放入n个不同盒子.这类问题实质上是一个重复排列的问题,可以用分步计数原理解决.第一个球有n种放法,第二个球有n种放法……第m个球有n种放法,故共有nm种不同放法.     

鸽巢问题的典型例题

<正>鸽巢原理又叫抽屉原理。抽屉原理一：如果将n+1 (n≥1)个物体任意放进n个抽屉里,那么至少有一个抽屉里放有两个或两个以上的物体。如,将5个苹果任意放进4个抽屉里,那么至少有一个抽屉里要放2个苹果。抽屉原理二：如果将多于m×n个物体任意放进n个抽屉里,那么至少有一个抽屉里放有m+1个物体或更多的物体。如,将17朵鲜花插进3只花瓶,那么至少有一只花瓶中插有6朵或更多的鲜花。     

生日的概率

367个人当中．肯定有2个人的生日相同,这是根据抽屉原理得到的结论。抽屉原理可以表述为：假如有N＋1个（或更多）物体装入到N个盒子．那么一定有某个盒子至少装有两个物体。一年里最多有366天（闰年才如此）．那么367个人当中肯定就会有两个人的生日在同一天．     

球入盒问题分类例析

一、球相同,盒子相同,且盒子不能空 例1：8个相同的球放入3个相同的盒子,每个盒子中至少有一个,问有多少种不同的放法？     

小学数学奥林匹克试题解题思路种种

如果把10本书放到9个抽屉里，那么可以肯定至少有一个抽屉里有两本或两本以上的书，这就是数学中的抽屉原理。抽屉原理的基本原理为：如果把(n 1)个元素放到n个抽屉里，那么至少有一个抽屉放有不止1个这种元素。