插板法

插板法

插板法指在解決若干相同元素分組,要求每組至少有一個元素,採用將比所需分組數目少1的板插入元素之間形成分組的解題策略。元素分組又分為相同元素分組和不相同元素分組這兩類問題。對於相同元素分組來說,如果是相同元素分到相同的組裡,問題就變的沒有意義,公考中也不會涉及到。那么對於相同元素分到不同的組裡,一般我們就用插板法來解決。

基本信息

定義

插板法就是在n個元素間的(n-1)個空中插入若干個(b)個板,可以把n個元素分成(b+1)組的方法
套用插板法必須滿足三個條件:
(1)這n個元素必須互不相異
(2)所分成的每一組至少分得一個元素
(3)分成的組別彼此相異

例子

插板法插板法
把10個相同的小球放入3個不同的箱子,每個箱子至少一個,問有幾種情況?
問題的題乾滿足條件(1)(2),適用插板法,c92=36
下面通過幾道題目介紹下插板法的套用
a湊元素插板法(有些題目滿足條件(1),不滿足條件(2),此時可適用此方法)

例1:把10個相同的小球放入3個不同的箱子,問有幾種情況?
3個箱子都可能取到空球,條件(2)不滿足,此時如果在3個箱子種各預先放入
1個小球,則問題就等價於把13個相同小球放入3個不同箱子,每個箱子至少一個,有幾種情況?
顯然就是c12 2=66
例2:把10個相同小球放入3個不同箱子,第一個箱子至少1個,第二個箱子至少3個,第三個箱子可以放空球,有幾種情況?
我們可以在第二個箱子先放入10個小球中的2個,小球剩8個放3個箱子,然後在第三個箱子放入8個小球之外的1個小球,則問題轉化為把9個相同小球放3不同箱子,每箱至少1個,幾種方法?c82=28
b添板插板法
例3:把10個相同小球放入3個不同的箱子,問有幾種情況?
-o-o-o-o-o-o-o-o-o-o-o表示10個小球,-表示空位
11個空位中取2個加入2塊板,第一組和第三組可以取到空的情況,第2組始終不能取空
此時若在第11個空位後加入第12塊板,設取到該板時,第二組取球為空
則每一組都可能取球為空c122=66
例4:有一類自然數,從第三個數字開始,每個數字都恰好是它前面兩個數字之和,直至不能再寫為止,如257,1459等等,這類數共有幾個?
因為前2位數字唯一對應了符合要求的一個數,只要求出前2位有幾種情況即可,設前兩位為ab
顯然a+b<=9,且a不為0
1-1-1-1-1-1-1-1-1--1代表9個1,-代表10個空位
我們可以在這9個空位中插入2個板,分成3組,第一組取到a個1,第二組取到b個1,但此時第二組始終不能取空,若多添加第10個空時,設取到該板時第二組取空,即b=0,所以一共有c102=45
例5:有一類自然數,從第四個數字開始,每個數字都恰好是它前面三個數字之和,直至不能再寫為止,如2349,1427等等,這類數共有幾個?
類似的,某數的前三位為abc,a+b+c<=9,a不為0
1-1-1-1-1-1-1-1-1---
在9個空位種插如3板,分成4組,第一組取a個1,第二組取b個1,第三組取c個1,由於第二,第三組都不能取到空,所以添加2塊板
設取到第10個板時,第二組取空,即b=0;取到第11個板時,第三組取空,即c=0。所以一共有c113=165
c選板法
例6:有10粒糖,如果每天至少吃一粒(多不限),吃完為止,求有多少種不同吃法?
o-o-o-o-o-o-o-o-o-oo代表10個糖,-代表9塊板
10塊糖,9個空,插入9塊板,每個板都可以選擇放或是不放,相鄰兩個板間的糖一天吃掉
這樣一共就是2^9=512啦
d分類插板
例7:小梅有15塊糖,如果每天至少吃3塊,吃完為止,那么共有多少種不同的吃法?
此問題不能用插板法的原因在於沒有規定一定要吃幾天,因此我們需要對吃的天數進行分類討論
最多吃5天,最少吃1天
1:吃1天或是5天,各一種吃法一共2種情況
2:吃2天,每天預先吃2塊,即問11塊糖,每天至少吃1塊,吃2天,幾種情況?c101=10
3:吃3天,每天預先吃2塊,即問9塊糖,每天至少1塊,吃3天?c82=28
4:吃4天,每天預先吃2塊,即問7塊糖,每天至少1塊,吃4天?c63=20
所以一共是2+10+28+20=60種
e二次插板法
例8:在一張節目單中原有6個節目,若保持這些節目相對次序不變,再添加3個節目,共有幾種情況?
-o-o-o-o-o-o-三個節目abc
可以用一個節目去插7個空位,再用第二個節目去插8個空位,用最後個節目去插9個空位
所以一共是c71×c81×c9 1=504種

相關搜尋

熱門詞條

聯絡我們