春季第四讲：三大原理（插板法，容斥原理，抽屉原理）

1、关于插班法的定义和使用条件：

       插板法就是在n个元素间的（n-1）个空中插入 若干个（b）个板，可以把n个元素分成（b+1）组的方法。
应用插板法必须满足三个条件：
（1） 这n个元素必须相同
（2） 所分成的每一组至少分得一个元素
  (3)    分成的组别彼此相异

【条件】把10苹果分给3个小朋友，每个小朋友至少一个，问有几种情况？
问题的题干满足 条件（1）（2），适用插板法，C9^2=36 。
 

例1 ：把10个相同的小球放入3个不同的箱子，问有几种情况？
3个箱子都可能取到空球，条件（2）不满足。此时如果在3个箱子种各预先放入1个小球，则问题就等价于把13个相同小球放入3个不同箱子，每个箱子至少一个，有几种情况？
显然就是C12^2=66。

 例2：把10个苹果分给3个小朋友，每个人至少有2个，共有多少种分法？
每个小朋友分至少分2个，肯定不满足条件2，所以我们进行了转换。

1）先让每个人分一个，剩下：10-3=7个；

2）而后从剩下的7个苹果中再分，保证每个人至少分一个：

所以最后的分法：C6^2=6×5÷2=15。

例3：（关于上次课堂例1的另一种解法）--------感兴趣的同学可以看看

利用补0的方法，让他们都变成4位数，然后使用插板法：

1）千位数有0：C12^2-3=63（之所以减去3，因为百位、十位和各位有可能是10，而这是不可能的。）

2）千位数是1：C11^2=55

3）所以2008排在：63+55+1=119

 

2、关于容斥原理的一些例题补充：

50名同学面向老师站成一行，老师先让大家从左至右按1，2，3，4，……，49，50依次报数；先让报数是5的倍数的同学向后转，再让报数是4的倍数的同学向后转，接着又让报数是6的倍数的同学向后转，这时面向老师的同学还有几名？

接析：

根据我们的分析，最后面向老师的必然有两种：转且转过两次的和没有转过的。

上图中划红线的就是我们所要求解的。

1）转且只转过两次：A交B+A交C+B交C-3 A交B交C=4+2+1-0=7；

2）没转过的：

转过的有：A并B并C=A+B+C-A交B-A交C-B交C+A交B交C=12+8+10-4-2-1+0=23；

没转过的：50-23=27.

所以最后老师的还有：27+7=34。

 附：有2000盏灯亮着的灯，各有一个拉线开关控制着，现按其顺序标号是1、2、3……、2000，然后将编号为2的倍数的灯线拉一下，再将编号为3的倍数的灯线拉一下，再将编号为5的倍数的灯线拉一下，3次拉完后亮着的灯有多少盏？（答案：1002）

 

 3、关于抽屉原理的一些例题和补充：

 1）例7：（题目省略）

【分析】内外环对转可以看成一个是静止的，只有一个环在转动，一个环转动一周后，每个滚珠都会有一次与标有相同数字的滚珠相对的局面出现，那么这种局面共要出现8次。将这8次局面看成8个苹果，注意到一环每转动45度角就有一次滚珠相对的局面出现，转动一周共有8次相对局面，而最初相对的滚珠所标的数字都不相同，所以相对的滚珠所标的数字相同的情况只出现在以后的7次转动中，将7次看成7个抽屉，根据抽屉原理至少有2次数字相对的局面出现在同一转动中，即必有某一时刻，内外环至少有两对数字相同的滚珠相对。

2）关于几何图形的抽屉原理：

      如图是一个3行10列共30个小正方形的长方形，现在把每个小方格涂上红色或黄色，请证明无论怎么涂法一定能找到两列，它们的涂色方式完全相同。

 

 【分析】根据题意，我们知道每一列涂上红色或者黄色共有以上8种情况（上图：注意图形的形状），我们可以将这8种情况看成8个抽屉，10列看成10个苹果。根据抽屉原理，有一抽屉至少有两个苹果。即：一定能找到两列，它们的涂色方式完全相同。

  3）关于最不利原则：

（2008日本小学奥林匹克）现有一袋子，里面装有8种不同颜色的玻璃球，每种颜色的玻璃球各有50个，则在这个袋子里至少要取出（    ）个玻璃球，才能保证取出的球至少有三种颜色，并且三种颜色的球都至少有10个。

【分析】：根据最不利原则：先取出两种颜色，各50个：50×2=100；

  其余颜色取出9个：6×9=54，再取1个就一定满足要求。

所以最后结果：50×2+9×6+1=155

二、学案答疑：

 1、提高班：

1）(题目略)

从整体和极端的角度考虑：最大的上升数是：123456789，并且这是符合要求的。从中去掉若干个数可以组成新的"上升数"。因而我们可以理解为：从1-9这9个数种，任意取出不同的数一定能组成“上升数”。

法1:每个数要么取，要么留，因而共有2^9 =502种组合。

法2:也可以进行任意取数：C9^2+C9^3+……+C9^9=2^9-C9^0-C9^1=502.

（小结：2^n=Cn^0+Cn^1+……+Cn^9）

2)(题目略)

【分析】要使得相邻两数互质，也就是要求奇数和偶数相邻排列时，即可。但要注意3和6不能排在一起。

所以我们先将奇数（1、3、5、7）进行全排列P4^4，而后使用插空法，一共有5个空，优先考虑6，6只能有3个空可放，其余偶数（2、4、8）在余下的4个空进行插空P4^3。

步步相乘，共有：P4^4×3×P4^3=24×3×24=1728.

3）（题目省略）

【分析】和的范围是1-21，而这些和当中能被3整除，而不能被5整除的数是：3、6、9、12、18、21，另外3与18，9与12的选法数目一一对应。分别对应有2、4、5、5、2、1中选取方法，共有2+4+5+5+2+1=19种选取方法。

2、尖子班：

1）(题目略)

和的取值范围是9-45，另外观察到第一组加数除以3余数是1，第二组加数除以3余数是2，说明他们的和必然是3的倍数。

9-45是3的倍数的个数一共有：（45-9）÷3+1=13.

 2）同提高学案3

3）（题目略)

 

直接使用树形图，根据对称原理首位1和5的六位数应该是相同的，首位是2和4的六位数是相同的，所以一共有：

9+18+18+18+9=72种。