活躍在競(jìng)賽中的幾何計(jì)數(shù)問題

●盧國興

(桐廬中學(xué) 浙江桐廬 311500)

幾何計(jì)數(shù)問題主要是指與幾何有關(guān)的計(jì)數(shù)問題，由于該類問題往往蘊(yùn)含著“形”的美妙與“數(shù)”的嚴(yán)謹(jǐn)，因此倍受競(jìng)賽命題者的青睞．

幾何計(jì)數(shù)問題的內(nèi)容比較別致，富于變化.如果自己不能理清思路，尋找到一種合適的解法，就很難得到正確的答案.以下筆者結(jié)合一些數(shù)學(xué)競(jìng)賽試題，介紹幾種典型的解法.

1 直接分類枚舉

當(dāng)對(duì)于原問題中的各種情形一時(shí)無法統(tǒng)一處理，并且注意到結(jié)論不是很龐大的數(shù)字時(shí)，不妨采用分類枚舉法．“直接分類枚舉”是一種最簡單、最基本的計(jì)數(shù)方法.

圖1

例1 聯(lián)結(jié)正五邊形A1A2A3A4A5的對(duì)角線交出另一個(gè)正五邊形B1B2B3B4B5，再次聯(lián)結(jié)正五邊形B1B2B3B4B5的對(duì)角線，又交出一個(gè)正五邊形C1C2C3C4C5(如圖1)，以圖中線段為邊的三角形中，共有等腰三角形

( )

A.50個(gè) B.75個(gè) C.85個(gè) D.100個(gè)

(2005年全國高中數(shù)學(xué)聯(lián)賽江西省初賽試題)

解 以A1為2條腰公共點(diǎn)的等腰三角形有6個(gè):△A1A2A5,△A1B3B4,△A1B2B5,△A1A3A4,△A1A2B5,△A1A5B2;

以B1為2條腰公共點(diǎn)的等腰三角形有9個(gè):△B1A3A4,△B1B2B5,△B1B3B4,△B1C3C4,△B1B2C5,△B1C2B5,△B1A2A5,△B1A3B4,△B1A4B3;

以C1為2條腰公共點(diǎn)的等腰三角形有2個(gè):△C1B3B3,△C1B2B5.

由于圖1中沒有等邊三角形，故每個(gè)等腰三角形的2條腰恰有一個(gè)公共頂點(diǎn)．因此,由對(duì)稱性可知共有等腰三角形5×(6+9+2)=85個(gè)．

例2 作正四面體每個(gè)面的中位線，共得12條線段，在這些線段中，求相互成異面直線的“線段對(duì)”的個(gè)數(shù)．

解 任取一條中位線AB，AB所在的側(cè)面沒有與AB異面的線段；含點(diǎn)A的另一個(gè)側(cè)面恰有一條中位線與AB異面；含點(diǎn)B的另一個(gè)側(cè)面也恰有一條中位線與AB異面；不含點(diǎn)A,B的側(cè)面恰有2條中位線與AB異面；因此與AB異面的中位線共有4條，即含有線段AB的異面“線段對(duì)”共有4個(gè)，于是得到異面“線段對(duì)”共有12×4=48個(gè)(其中有重復(fù))．

但每一個(gè)異面“線段對(duì)”中有2條線段，故恰好被計(jì)算了2次，因此,得到48÷2=24個(gè)異面“線段對(duì)”．

在直接分類枚舉時(shí)，必須注意無一重復(fù)、無一遺漏，要有規(guī)律地進(jìn)行.

2 運(yùn)用2個(gè)原理

分類計(jì)數(shù)原理與分步計(jì)數(shù)原理是解決組合計(jì)數(shù)問題的2種基本思想方法，是解決計(jì)數(shù)問題的基礎(chǔ).合理運(yùn)用2個(gè)原理可以順利解決一些簡單的幾何計(jì)數(shù)問題．

圖2

例3 在一個(gè)正六邊形的6個(gè)區(qū)域中栽種觀賞植物(如圖2)，要求在同一個(gè)區(qū)域中種同一種植物，相鄰的2個(gè)區(qū)域種不同的植物．現(xiàn)有4種不同的植物可供選擇，則有______種栽種方法.

(2001年全國高中數(shù)學(xué)聯(lián)賽試題)

解 將6個(gè)區(qū)域依次標(biāo)上字母A,B,C,D,E,F，按A,C,E種植植物的種數(shù)進(jìn)行討論：

(1)若A,C,E種同一種植物，有4種種法．當(dāng)A,C,E種植后，B,D,F可從剩余的3種植物中各選一種植物(允許重復(fù))，各有3種方法．此時(shí)共有4×3×3×3=108種種植方法.

根據(jù)分類計(jì)數(shù)原理，共有N=108+432+192=732種栽種方案．

圖3

評(píng)注 事實(shí)上本題是一個(gè)環(huán)形排列問題,可作如下推廣:已知P是n(n≥3)邊形內(nèi)的一點(diǎn)，它與n個(gè)點(diǎn)相連構(gòu)成n個(gè)三角形，取k(k≥2)種顏色對(duì)這n個(gè)三角形涂色，要求相鄰2個(gè)三角形所涂顏色不同，試求涂色的方案有多少種?

例4 如圖3，點(diǎn)P1,P2,…,P10分別是四面體的頂點(diǎn)或棱的中點(diǎn)，那么在同一平面上的四點(diǎn)組(P1,Pi,Pj,Pk) (1

(2002年全國高中數(shù)學(xué)聯(lián)賽試題)

解 可分為2類情況討論:

(2)含P1的每條棱上三點(diǎn)組添加底面與它異面的那條棱上的中點(diǎn)組成的四點(diǎn)組也在一個(gè)平面上，這樣的四點(diǎn)組有3個(gè).

3 考慮間接方法

著名數(shù)學(xué)家華羅庚曾說：“善于‘退’，足夠地‘退’，‘退’到最原始而不是去重要性的地方，是學(xué)好數(shù)學(xué)的一個(gè)訣竅.”對(duì)于有些幾何計(jì)數(shù)問題，當(dāng)正向思維受阻或需迂回曲折方能達(dá)到目的時(shí)，用間接法往往能開拓新的解題途徑，得出簡捷甚至奇異的解，效果更甚．

例5 在正2 006邊形中，與所有邊均不平行的對(duì)角線的條數(shù)為

( )

A.2 006 B.1 0032

C.1 0032-1 003 D．1 0032-1 002

(2006年全國高中數(shù)學(xué)聯(lián)賽浙江省初賽試題)

例6 平面上有5個(gè)點(diǎn)，任意兩點(diǎn)之間用線段連接，這些線段互不平行，互不垂直，也不重合，過其中每個(gè)點(diǎn)，都向其他4個(gè)點(diǎn)間的線段作垂線，所有這些垂線的交點(diǎn)至多有多少個(gè)？

(第6屆IMO試題)

綜上所述，這些垂線的交點(diǎn)至多有435-30-20-75=310個(gè)．4 特殊問題一般化

在數(shù)學(xué)學(xué)習(xí)過程中，我們經(jīng)常會(huì)將一個(gè)數(shù)學(xué)問題特殊化，從而得到需要的結(jié)果，提高解題的效率.但有時(shí)也可將一個(gè)特殊問題進(jìn)行一般化地研究，讓待解決的問題置于更為一般情形之中，揭示其問題本質(zhì)，從而解決這一特殊問題或類似問題.對(duì)于有些計(jì)數(shù)問題，我們利用這種“特殊問題一般化”的思考方法，其結(jié)果會(huì)讓人有種“柳暗花明又一村”的感覺．

例7 用5種不同的顏色給圖4中“五角星”的5個(gè)頂點(diǎn)染色(每個(gè)點(diǎn)染一種顏色，有的顏色也可以不用)，使每條線段上的2個(gè)頂點(diǎn)皆不同色，則不同的染色方法有種______．

(2005年全國高中數(shù)學(xué)聯(lián)賽江西省初賽試題)

圖4

解 將其轉(zhuǎn)化為：具有5個(gè)扇形格的圓盤染5種顏色，使得鄰格不同色的染色問題．設(shè)有k個(gè)扇形格的圓盤染5種顏色的方法數(shù)為xk，則

xk+xk-1=5·4k-1，

于是x5= (x5+x4)-(x4+x3)+(x3+x2)-x2=

5(44-43+42-4)=1 020.

因此，不同的染色方法有1 020種．

圖5

例8 對(duì)一個(gè)邊長互不相等的凸n(n≥3)邊形的邊染色，每條邊可以染紅、黃、藍(lán)3種顏色中的一種，但是不允許相鄰的邊有相同的顏色．問：共有多少種不同的染色方法？

(2006年全國高中數(shù)學(xué)聯(lián)賽

上海市初賽試題)

解 設(shè)不同的染色法有pn種．易知p3=6．當(dāng)n≥4時(shí)，如圖5,對(duì)于邊a1，有3種不同的染法，因?yàn)檫卆2的顏色與邊a1的顏色不同，所以對(duì)邊a2有2種不同的染法，類似地，對(duì)邊a3，…，邊an-1均有2種染法．對(duì)于邊an，用與邊an-1不同的2種色染色，但是，這樣也包括了它與邊a1顏色相同的情況，而邊a1與邊an顏色相同的不同染色方法數(shù)就是凸n-1邊形的不同染色方法數(shù)的種數(shù)pn-1.因此

pn=3×2n-1-pn-1，

pn-2n=-(pn-1-2n-1),

于是pn-2n=(-1)n-3(p3-23)=(-1)n-2·2，

pn=2n+(-1)n·2 (n≥3).

綜上所述，不同的染色方法數(shù)為

pn=2n+(-1)·2．

5 構(gòu)造一一對(duì)應(yīng)

利用對(duì)應(yīng)(或映射)來解決計(jì)數(shù)問題，就是通過建立集合A與另一集合B之間的對(duì)應(yīng)(或映射)，把對(duì)集合A的計(jì)數(shù)轉(zhuǎn)化為對(duì)集合B的計(jì)數(shù)．實(shí)現(xiàn)這種轉(zhuǎn)化的關(guān)鍵是：(1)選擇適當(dāng)?shù)谋阌谟?jì)數(shù)的集合；(2)建立集合間的對(duì)應(yīng)(或映射)關(guān)系．

例9 設(shè)有一個(gè)凸n邊形，不相鄰的2個(gè)頂點(diǎn)的連線叫做它的對(duì)角線．假設(shè)沒有3條對(duì)角線交于凸n邊形內(nèi)部一點(diǎn)，求這些對(duì)角線兩兩相交(在凸n邊形內(nèi)部)的交點(diǎn)總數(shù)．

(1955年普特南數(shù)學(xué)奧林匹克競(jìng)賽試題)

評(píng)注 本題的結(jié)論是幾何計(jì)數(shù)中一個(gè)重要的結(jié)論,可用它解決一些較復(fù)雜的幾何計(jì)數(shù)問題.

圖6

例10 如圖6，在8×8的棋盤上取出一個(gè)由4個(gè)小方格組成的凸字形，問共有多少種不同的取法？

解 把凸字形上面的那個(gè)小方格稱為它的頭，則每個(gè)凸字形恰好有一個(gè)頭，按凸字形的頭在棋盤的邊框或內(nèi)部，把凸字形分為2類：

(1)當(dāng)凸字形的頭在棋盤的邊框時(shí)，則除盤上4個(gè)角外，邊框上其余的每個(gè)方格都唯一地對(duì)應(yīng)著凸字形的一種取法，共有4×6=24種取法；

(2)當(dāng)凸字形的頭在棋盤內(nèi)部時(shí)，則棋盤內(nèi)部的每個(gè)方格都對(duì)應(yīng)著凸字形的4種取法,而棋盤內(nèi)部有6×6=36個(gè)方格，因此凸字形共有4×36=144種取法.

由分類計(jì)數(shù)原理知，共有24+144=168種不同的取法．

6 用數(shù)學(xué)歸納法

例11 設(shè)O是邊長為1的方格紙上的一個(gè)固定的結(jié)點(diǎn).現(xiàn)以Pk表示方格紙上的以點(diǎn)O為起點(diǎn)、長度為k且各段都位于網(wǎng)格線上的所有不同折線的條數(shù),求證:對(duì)所有k,都有Pk<2×3k.

(第22屆莫斯科數(shù)學(xué)奧林匹克競(jìng)賽試題)

證明 (用數(shù)學(xué)歸納法)

(1)當(dāng)k=1時(shí),有P1≤4<2×3成立;

(2)假設(shè)當(dāng)k=m時(shí)，結(jié)論成立，則當(dāng)k=m+1時(shí),對(duì)于任何一條長度為m+1的滿足要求的折線,去掉其最后長度為1的部分,就得到一條長度為m且滿足要求的折線.在這個(gè)對(duì)應(yīng)過程中,至多有3條長為m+1的折線對(duì)應(yīng)于同一條長度為m的折線,因此

Pm+1≤3Pm<3×2×3m=2×3m-1,

即當(dāng)k=m+1時(shí)，結(jié)論也成立.

由(1),(2)可知結(jié)論對(duì)任何k∈N*都成立.

例12 圓上有n個(gè)點(diǎn)(n>1),聯(lián)結(jié)這n個(gè)點(diǎn),依次記為P1,P2，…,Pn,使得折線P1P2…Pn不相交,問這樣的聯(lián)結(jié)方法有多少種?

解 先用數(shù)學(xué)歸納法證明:在點(diǎn)Pn確定的情況下,可聯(lián)結(jié)的方法數(shù)有2n-2(n≥2)種:

(1)當(dāng)n=2時(shí),聯(lián)結(jié)P1P2只有1種方法,即1=22-2成立;

(2)假設(shè)當(dāng)n=k(k≥2,k∈N)時(shí)，有2k-2種聯(lián)結(jié)方法，則當(dāng)n=k+1時(shí),由于對(duì)每一種聯(lián)結(jié)Pk+1的方法,Pk+1必須在P1和Pk之間,因此,連成的折線或是P1P2…PkPk+1,或是Pk+1P1P2…Pk,即有2種可能的選擇.由此可得,k+1個(gè)點(diǎn)有2×2k-2=2(k+1)-2種聯(lián)法,即當(dāng)n=k+1時(shí)結(jié)論也成立.

由(1),(2)可得在點(diǎn)Pn確定的情況下,可聯(lián)結(jié)的方法數(shù)有2n-2(n≥2)種.另外,注意到點(diǎn)Pn的選擇有n種,因此,符合題意的聯(lián)結(jié)方法數(shù)為n·2n-2種.

計(jì)數(shù)問題是數(shù)學(xué)中重要研究對(duì)象之一，通過對(duì)計(jì)數(shù)方法的學(xué)習(xí)和應(yīng)用，既可以讓學(xué)生掌握相關(guān)的數(shù)學(xué)內(nèi)容，處理一些計(jì)數(shù)問題，又可以培養(yǎng)學(xué)生的數(shù)學(xué)意識(shí),提升數(shù)學(xué)思想.