初一數(shù)學(xué)競賽講座⑽

1、數(shù)學(xué)競賽教材系列初一數(shù)學(xué)競賽講座第10講 計數(shù)的方法與原理計數(shù)方法與原理是組合數(shù)學(xué)的主要課題之一，本講介紹一些計數(shù)的基本方法及計數(shù)的基本原理。一、枚舉法一位旅客要從武漢乘火車去北京，他要了解所有可供乘坐的車次共有多少，一個最易行的辦法是找一張全國列車運行時刻表，將所有從武漢到北京的車次逐一挑出來，共有多少次車也就數(shù)出來了，這種計數(shù)方法就是枚舉法。所謂枚舉法，就是把所要求計數(shù)的所有對象一一列舉出來，最后計算總數(shù)的方法。運用枚舉法進(jìn)行列舉時，必須注意無一重復(fù)，也無一遺漏。例1 四個學(xué)生每人做了一張賀年片，放在桌子上，然后每人去拿一張，但不能拿自己做的一張。問：一共有多少種不同的方法？解：設(shè)四個學(xué)生

2、分別是A，B，C，D，他們做的賀年片分別是a，b，c，d。先考慮A拿B做的賀年片b的情況（如下表），一共有3種方法。同樣，A拿C或D做的賀年片也有3種方法。一共有333=9（種）不同的方法。例2 甲、乙二人打乒乓球，誰先連勝兩局誰贏，若沒有人連勝頭兩局，則誰先勝三局誰贏，打到?jīng)Q出輸贏為止。問：一共有多少種可能的情況？解：如下圖，我們先考慮甲勝第一局的情況：圖中打的為勝者，一共有7種可能的情況。同理，乙勝第一局也有 7種可能的情況。一共有 77=14（種）可能的情況。二、加法原理如果完成一件事情有n類方法，而每一類方法中分別有m1，m2，mn種方法，而不論采用這些方法中的任何一種，都能單獨地完成

3、這件事情，那么要完成這件事情共有：N=m1+m2+mn種方法。這是我們所熟知的加法原理，也是利用分類法計數(shù)的依據(jù)。例3 一個自然數(shù)，如果它順著數(shù)和倒著數(shù)都是一樣的，則稱這個數(shù)為“回文數(shù)”。例如1331，7，202都是回文數(shù)，而220則不是回文數(shù)。問：1到6位的回文數(shù)一共有多少個？按從小到大排，第2000個回文數(shù)是多少？解：一位回文數(shù)有：1，2，9，共9個；二位回文數(shù)有：11，22，99，共9個；三位回文數(shù)有：101，111，999，共90個；四位回文數(shù)有：1001，1111，9999，共90個；五位回文數(shù)有：10001，10101，99999，共900個；六位回文數(shù)有：100001，10110

4、1，999999，共900個。到六位數(shù)為止，回文數(shù)共有999090900900=1998（個）。第1999個回文數(shù)是1000001，第2000個回文數(shù)是1001001。例4 設(shè)有長度為1，2，9的線段各一條，現(xiàn)在要從這9條線段中選取若干條組成一個正方形，共有多少種不同的取法？這里規(guī)定當(dāng)用2條或多條線段接成一條邊時，除端點外，不許重疊。解法1：因為所以正方形的邊長不大于11。下面按正方形的邊長分類枚舉：（1）邊長為11：92=8+3=74=65，可得1種選法；（2）邊長為10：91=82=73=64，可得1種選法；（3）邊長為 9：9=81=72=63=54，可得5種選法；（4）邊長為8：8=7

5、1=62=5+3，可得1種選法；（5）邊長為7：7=61=52=43，可得1種選法；（6）邊長6時，無法選擇。綜上計算，不同的取法共有11+511=9（種）。解法2：由于這些線段互不等長，故至少要用7條線段才能組成一個正方形。當(dāng)恰取7條線段組成正方形時，正方形的3條邊各用2條線相接，另一條邊只用一條線段；當(dāng)恰用8條線段時，只能每邊各用2條線段相接（容易看出，其他情況不可能發(fā)生）。因為 1+29=45， 45不能被4整除，所以用9條線段，不可能組成正方形。由解法一知，拼出的正方形邊長至多為11，又易知正方形的邊長不可能為1，2，3，4，5，6。有了以上分析就容易計數(shù)了。（1）取出7條線段，有以下

6、7種：7=1+62534；81+72+635；9182736=45（這個式子有5種）；（2）取出8條線段，有以下2種：19283746；29384756。綜上所述，不同的取法共有72=9（種）。三、乘法原理如果完成一件事必須分n個步驟，而每一個步驟分別有m1，m2，mn種方法，那么完成這件事共有：Nm1×m2××mn種方法。這就是乘法原理，它是分步法的依據(jù)。乘法原理和加法原理被稱為是計數(shù)的基本原理。我們應(yīng)注意它們的區(qū)別，也要注意二者的聯(lián)合使用。例5 一臺晚會上有6個演唱節(jié)目和4個舞蹈節(jié)目。求：（1）當(dāng)4個舞蹈節(jié)目要排在一起時，有多少不同的安排節(jié)目的順序？（2）當(dāng)要

7、求每2個舞蹈節(jié)目之間至少安排1個演唱節(jié)目時，一共有多少不同的安排節(jié)目的順序？解：（1）先將4個舞蹈節(jié)目看成1個節(jié)目，與6個演唱節(jié)目一起排，有 7！=7×6×5×4×3×2×1=5404（種）方法。第二步再排4個舞蹈節(jié)目，有4！=4×3×2×124（種）方法。根據(jù)乘法原理，一共有 5040×24=120960（種）方法。（2）首先將6個演唱節(jié)目排成一列（如下圖中的“”），一共有6！=6×5×4×3×2 ×1=720（種）方法。××

8、;×××××第二步，再將4個舞蹈節(jié)目排在一頭一尾或2個演唱節(jié)目之間（即上圖中“×”的位置），這相當(dāng)于從7個“×”中選4個來排，一共有7×6×5×4840（種）方法。根據(jù)乘法原理，一共有720×840=604800（種）方法。例6 有8個隊參加比賽，如果采用下面的淘汰制，那么在賽前抽簽時，實際上可以得到多少種不同的安排表？解：8個隊要經(jīng)過3輪比賽才能確定冠亞軍。將第1輪的4組，自左至右記為1，2，3，4組，其中第1，2組為甲區(qū)，3，4組為乙區(qū)。8個隊抽簽即是在上圖的8個位置排列，共有8！

9、=8×7×6×5×4×3×2×1=40320（種）不同的方法。但是，兩種不同的排列不一定是實際上不同比賽的安排表。事實上，8隊中的某4隊都分在甲區(qū)或乙區(qū)，實際上是一樣的；同區(qū)的4隊中某2隊在某一組或另一組，實際上也是一樣的；同組中的2隊，編號誰是奇數(shù)誰是偶數(shù)實際也是一樣的。由乘法原理知，在40320種排法中，與某一種排法實質(zhì)上相同的排法有 2×22×24=27=128（種），故按實際不同比賽安排表的種數(shù)是四、對應(yīng)法小孩子數(shù)蘋果，往往掰著手指頭，一個一個地掰，掰完左手掰右手，這種數(shù)蘋果的方法就是對應(yīng)法。小孩

10、子把蘋果與自己的手指頭一對一，他掰了幾個指頭，也就數(shù)出了幾個蘋果。一般地，如果兩類對象彼此有一對一的關(guān)系，那么我們可以通過對一類較易計數(shù)的對象計數(shù)，而得出具有相同數(shù)目的另一類難于計數(shù)的對象的個數(shù)。例7 在8×8的方格棋盤中，取出一個由 3個小方格組成的“L”形（如圖1），一共有多少種不同的方法？解：每一種取法，有一個點與之對應(yīng)，這就是圖1中的A點，它是棋盤上橫線與豎線的交點，且不在棋盤邊上。從圖2可以看出，棋盤內(nèi)的每一個點對應(yīng)著4個不同的取法（“L”形的“角”在2×2正方形的不同“角”上）。由于在 8×8的棋盤上，內(nèi)部有7×7=49（個）交叉點，故不同的

11、取法共有49×4=196（種）。例8 數(shù)3可以用4種方法表示為1個或幾個正整數(shù)的和，如3，12，2+1，1+11。問：1999表示為1個或幾個正整數(shù)的和的方法有多少種？分析與解：我們將1999個1寫成一行，它們之間留有1998個空隙，在這些空隙處，或者什么都不填，或者填上“”號。例如對于數(shù)3，上述4種和的表達(dá)方法對應(yīng)：111，111，111，111。顯然，將1999表示成和的形式與填寫1998個空隙處的方式之間一對一，而每一個空隙處都有填“”號和不填“”號2種可能，因此1999可以表示為正整數(shù)之和的不同方法有五、容斥原理在應(yīng)用加法原理時，關(guān)鍵在于把所要計數(shù)的對象分為若干個不重不漏的類

12、，使得每類便于計數(shù)。但是具體問題往往是復(fù)雜的，常常扭成一團(tuán)，難以分為不重不漏的類，而要把條理分清楚就得用加法原理的推廣容斥原理。為了表達(dá)方便，我們用A表示A類元素的個數(shù)，用B表示B類元素的個數(shù)，用 AB表示是 A類或是 B類元素的個數(shù)，用AB表示既是A類又是B類元素的個數(shù)。ABC，ABC的意義類似。容斥原理1 如果被計數(shù)的事物有兩類，那么ABABAB。容斥原理2 如果被計數(shù)的事物有三類，那么ABCA+BC-AB-BCACABB。容斥原理的實質(zhì)在于包含與排除，或形象地稱之為“多退少補(bǔ)”。容斥原理若用韋恩圖進(jìn)行分析和記憶，十分方便，留給讀者研究。例9 在100名學(xué)生中，有10人既不會騎自行車又不會

13、游泳，有65人會騎自行車，有73人會游泳，既會騎自行車又會游泳的有多少人？解：從100名總?cè)藬?shù)中減去既不會騎自行車又不會游泳的10人，就是會騎自行車或會游泳的人數(shù)100-10=90（人）。既會騎自行車又會游泳的有（6573）90=48（人）。例10 在1至100的自然數(shù)中，不能被2整除，又不能被3整除，還不能被5整除的數(shù)，占這100個自然數(shù)的百分之幾？解：由容斥原理2知，1至100的自然數(shù)中，或能被2整除，或能被3整除，或能被5整除的自然數(shù)的個數(shù)是503320-16-6374。所以，在1至100的自然數(shù)中，不能被2整除，又不能被3整除，還不能被5整除的自然數(shù)有10074=26（個），占這100

14、個自然數(shù)的26。六、歸納法對于比較復(fù)雜的問題，可以先觀察其簡單情況，歸納出其中帶規(guī)律性的東西，然后再來解決較復(fù)雜的問題。例11 10個三角形最多將平面分成幾個部分？解。設(shè)n個三角形最多將平面分成an個部分。n=1時，a1=2；n=2時，第二個三角形的每一條邊與第一個三角形最多有2個交點，三條邊與第一個三角形最多有2×3=6（個）交點。這6個交點將第二個三角形的周邊分成了6段，這6段中的每一段都將原來的每一個部分分成2個部分，從而平面也增加了6個部分，即a222×3。n3時，第三個三角形與前面兩個三角形最多有4×312（個）交點，從而平面也增加了12個部分，即：a3

15、=22×34×3。一般地，第n個三角形與前面（n-1）個三角形最多有2（n-1）×3個交點，從而平面也增加2（n1）×3個部分，故an=22×34×32（n-1）×32242（n-1）×323n（n-1）3n2-3n2。特別地，當(dāng)n10時，a103×1023×102=272，即10個三角形最多把平面分成272個部分。七、整體法解答數(shù)學(xué)題，有時要“化整為零”，使問題變得簡單；有時反而要從整體上來考慮，從全局、從整體來研究問題。例12 正方形ABCD的內(nèi)部有1999個點，以正方形的4個頂點和內(nèi)部的1

16、999個點為頂點，將它剪成一些三角形。問：一共可以剪成多少個三角形？共需剪多少刀？解：我們從整體來考慮，先計算所有三角形的內(nèi)角和。匯聚在正方形內(nèi)一點的諸角之和是360°，而正方形內(nèi)角和也是360°，共有 360°×1999360°，從而三角形的個數(shù)是由于每個三角形有三條邊，而正方形紙原來的4條邊當(dāng)然不用剪；其余的邊，由于是兩個三角形的公共邊，剪一刀出兩條邊，所以共剪的刀數(shù)是練習(xí)10 1一只青蛙在A，B，C三點之間跳動，若青蛙從A點跳起，跳4次仍回到A點，則這只青蛙一共有多少種不同的跳法？2在國際象棋棋盤上放置兩只“車”，如果它們彼此不構(gòu)成威脅，

17、那么一共有多少種不同的放法？3在8×8的棋盤上可以找到多少個形如右圖所示的“凸”字形圖形？4從19，20，21，97，98，99這81個數(shù)中，選取兩個不同的數(shù)，使其和為偶數(shù)的選法總數(shù)是多少？5平面上有7個不在同一直線上的點，以這7個點作為頂點做三角形，使得任何兩個三角形至多只有一個公共頂點。最多可做出多少個滿足條件的三角形？6下圖是一個道路圖。A處有一大群孩子，這群孩子向東或向北走，在從A開始的每個路口，都有一半人向北走，另一半人向東走，如果先后有60個孩子到過路口B，那么先后共有多少個孩子到過路口C？7在1001，1002，2000這1000個自然數(shù)中，可以找到多少對相鄰的自然數(shù)，

18、使它們相加時不進(jìn)位？8有10個箱子，編號為1，2，10，各配一把鑰匙，10把各不相同，每個箱子放進(jìn)一把鑰匙鎖好，先撬開1，2號箱子，取出鑰匙去開別的箱子，如果最終能把所有箱子的鎖都打開，則說是一種好的放鑰匙的方法。求好的方法的總數(shù)。練習(xí)10答案 1.6種。解：如下圖，第1步跳到B，4步回到A有3種方法；同樣第1步到C的也有3種方法。共有6種方法。2.3136種。解：第一步，放第一只“車”，有64種方法；第二步，放第二只“車”，因不能和第一只同行，也不能同列，故有49種方法。由乘法原理，一共有64×49=3136（種）放法。3.168個。解：在每個2×3的長方形中可以找到2個

19、“凸”字形圖形，8×8方格棋盤中共有84個2×3的長方形，所以可以找到84×2=168（個）。4.1600種。解：從19到99共計81個不同的整數(shù)，其中有41個奇數(shù)、40個偶數(shù)。若選取兩數(shù)之和為偶數(shù)，則必須且只須選取的兩個數(shù)有相同的奇偶性，所以選取的方法數(shù)分為兩類：第一類，選取兩個不同偶數(shù)的方法數(shù)；第二類，選取兩個不同奇數(shù)的方法數(shù)。依加法原理，這兩類方法數(shù)的總和即為所求的方法數(shù)。第一類是從40個偶數(shù)中選取兩個不同偶數(shù)的方法數(shù)，先取第一個偶數(shù)有40種方法，從其余39個偶數(shù)中選擇第2個有39種方法，依乘法原理，共有40×39種不同的方法，但注意選取第1個數(shù)比如30，選取第 2個數(shù)比如 32，與選第1個數(shù)32，再選第2個數(shù)30，是同一組。所以總的選法數(shù)應(yīng)該折半，第二類是從41個奇數(shù)中選取兩個不同奇數(shù)的方法數(shù)，與上述方法相同