三類傳球問題的對(duì)應(yīng)解法*

武漢華中師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院(430079) 陳 欣 胡典順

三類傳球問題的對(duì)應(yīng)解法*

武漢華中師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院(430079) 陳 欣 胡典順

傳球問題是排列組合中的經(jīng)典名題,在許多中學(xué)數(shù)學(xué)刊物中,有關(guān)傳球問題的研究多數(shù)僅限于對(duì)傳球方式不加限制的情況.對(duì)此,筆者做了進(jìn)一步思索,舉一反三,對(duì)傳球方式加以限定,得到了三類傳球問題,并通過建立一一對(duì)應(yīng)的數(shù)學(xué)模型,將傳球問題轉(zhuǎn)化為我們已經(jīng)解決的熟悉問題,得到了不同限制條件下三類傳球問題的對(duì)應(yīng)解法.

題型一m(m≥3)個(gè)人A1,A2,...,Am圍成一圈相互傳球,首先由A1發(fā)球作為第一次傳球,經(jīng)過n(n≥3)次傳球,球又回到A1手中,試求所有傳球方式的種數(shù)an.

題型二m(m≥3)個(gè)人A1,A2,...,Am圍成一圈相互傳球,規(guī)定每次只能把球傳給相鄰的人,首先由A1發(fā)球作為第一次傳球,經(jīng)過n(n≥3)次傳球,球又回到A1手中,試求所有傳球方式的種數(shù)an.

題型三m(m≥6)個(gè)人A1,A2,...,Am圍成一圈相互傳球,規(guī)定每次只能把球傳給與自己不相鄰的人,且每人至多只傳一次球.經(jīng)過4次傳球,球又回到A1手中,試求所有傳球方式的種數(shù)Am.

1.題型一?染色問題

此類傳球問題對(duì)傳球方式不加限制,一般地,可以通過分類討論找到數(shù)列{an}的遞推關(guān)系式,再進(jìn)行求解.由于持球人不能把球傳給自己,只能傳給其他m-1個(gè)人中的任何一個(gè),這一類型的傳球問題與“染色問題”有著千絲萬縷的聯(lián)系(詳見文[1]).

圖1

建立對(duì)應(yīng)關(guān)系

我們將此問題與“染色問題”建立對(duì)應(yīng)關(guān)系.如果把從A1開始傳球最后回到A1手中每個(gè)環(huán)節(jié)的人員按照傳球次序順次放入圖1中對(duì)應(yīng)的n個(gè)區(qū)域O1,O2,...,On(n≥3), (其中起始的A1和結(jié)束的A1都放入O1區(qū)域),由于持球人不能把球傳給自己,故相鄰兩區(qū)域的人員不同,那么問題本質(zhì)就是：用m(m≥3)種顏色A1,A2,...,Am給圖1中的n(n≥3)個(gè)區(qū)域O1,O2,...,On染色,要求相鄰區(qū)域不同色且區(qū)域O1的顏色固定的所有染色方法.

問題解答

設(shè)an為符合要求的染色方法數(shù).則易知a3=(m-1)(m-1).不妨設(shè)n≥4,規(guī)定O1區(qū)域必須染A1這種顏色,O2與O1不同色,O2有m-1種染法.同理,O3與O2不同色,O3有m-1種染法,...,On與On-1不同色,On有m-1種染法,這共有(m-1)n-1種不同染法.但以上染法中包含了O1與On同色的情形,此時(shí)可將O1與On視為同一個(gè)區(qū)域,這樣的染法恰為an-1種,因此我們得出：

可通過構(gòu)造等比數(shù)列求得：

由于每一種染色方案對(duì)應(yīng)一種傳球方式,故符合要求的傳球方式有種.

染色問題是我們非常熟悉的題型,將傳球問題轉(zhuǎn)化為染色問題后,題目變得更加直觀、淺顯.

圖2

例1 4人進(jìn)行傳球練習(xí),要求每人接球后再傳給別人,由甲開始發(fā)球,并作為第一次傳球,經(jīng)5次傳球后,球又回到甲手中,問：共有多少種傳球方式?

可將此題轉(zhuǎn)化為：用紅、黃、藍(lán)、綠4種顏色,給圖2區(qū)域染色,規(guī)定A區(qū)域染紅色且相鄰區(qū)域的顏色不同,問：共有多少種染色方法?

建立對(duì)應(yīng)關(guān)系求解問題,在看似沒有聯(lián)系的兩類問題之間搭建橋梁,悄然發(fā)現(xiàn)許多問題都是殊途同歸,萬象歸一.

2.題型二?動(dòng)點(diǎn)問題

雖然此題在題型一基礎(chǔ)上只增加了限制條件“只能把球傳給相鄰的人”,但在解法上卻截然不同,需要重新構(gòu)造與之對(duì)應(yīng)的模型.

建立對(duì)應(yīng)關(guān)系

我們規(guī)定傳球過程中順時(shí)針傳球?yàn)檎?逆時(shí)針傳球?yàn)樨?fù)向,設(shè)n次傳球中有x次正向傳球,n-x次負(fù)向傳球.

在動(dòng)點(diǎn)運(yùn)動(dòng)問題中有以下題型：一動(dòng)點(diǎn)從原點(diǎn)出發(fā),在數(shù)軸上運(yùn)動(dòng),每次只能向左或向右運(yùn)動(dòng)一個(gè)單位長度,經(jīng)過n(n≥3)次運(yùn)動(dòng)后,該點(diǎn)所處位置的坐標(biāo)為m(m∈N?)的整數(shù)倍,問：該點(diǎn)的運(yùn)動(dòng)方式共有多少種?

該題型與題型二存在以下對(duì)應(yīng)關(guān)系：

(1)A1所在位置相當(dāng)于數(shù)軸原點(diǎn);

(2)n次傳球?qū)?yīng)動(dòng)點(diǎn)的n次運(yùn)動(dòng),順時(shí)針傳球一次相當(dāng)于點(diǎn)向右運(yùn)動(dòng)一個(gè)單位,逆時(shí)針傳球一次相當(dāng)于點(diǎn)向左運(yùn)動(dòng)一個(gè)單位;

(3)球最后回到A1手中必符合以下三種情形之一：

①正向傳球和負(fù)向傳球的次數(shù)一樣多;

②正向傳球次數(shù)比負(fù)向傳球次數(shù)多時(shí),多的次數(shù)必為m的正整數(shù)倍;

③負(fù)向傳球次數(shù)比正向傳球次數(shù)多時(shí),多的次數(shù)也必為m的正整數(shù)倍.

以上三種情形都相當(dāng)于點(diǎn)到達(dá)位置的坐標(biāo)為km(k∈Z),其中k=0時(shí)意為正、負(fù)向傳球次數(shù)一樣多;k＞0時(shí)意為正向傳球次數(shù)比負(fù)向傳球次數(shù)多,k＜0時(shí)意為負(fù)向傳球次數(shù)比負(fù)向傳球次數(shù)多.

(4)點(diǎn)的每一種運(yùn)動(dòng)方式對(duì)于一種傳球方式.

問題解答

n次運(yùn)動(dòng)后點(diǎn)處位置的坐標(biāo)為m(m∈N?)的整數(shù)倍,x應(yīng)滿足條件：x-(n-x)=km(k∈Z),即2x-n=km(k∈Z).對(duì)于該方程的每一個(gè)自然數(shù)解x0,對(duì)應(yīng)著點(diǎn)的運(yùn)動(dòng)方式有種(向右運(yùn)動(dòng)x0次,向左運(yùn)動(dòng)n-x0次).故點(diǎn)的運(yùn)動(dòng)方式共種,其中

所以,不同傳球種數(shù)

以上解答簡潔有效,避免了分類討論帶來的麻煩,可見,通過建立對(duì)應(yīng)關(guān)系將原題題設(shè)進(jìn)行等價(jià)轉(zhuǎn)換,轉(zhuǎn)換成熟悉的易于理解的題型,是一種重要且有效的解題途徑.

另外,還可變化題型背景將題型二改編為青蛙跳動(dòng)問題.

例2 某青蛙在池塘中的荷葉上跳動(dòng),荷葉排列成一圈,青蛙只能在相鄰的兩片荷葉上跳動(dòng),如果池塘中共有10片荷葉,問：青蛙跳14次后恰好回到出發(fā)荷葉上的跳動(dòng)方法.

解 設(shè)青蛙順時(shí)針跳動(dòng)x(0≤x≤14,x∈N)次,逆時(shí)針跳動(dòng)14-x次,則

得到x可以取2,7,12.故青蛙跳動(dòng)方法種數(shù)為種.

3.題型三?站位問題

題型三中有4次傳球,規(guī)定每次只能把球傳給與自己不相鄰的人且每人至多只傳一次球,故除A1以外還有3個(gè)人傳了球,建立對(duì)應(yīng)將此問題轉(zhuǎn)化為“站位問題”.

建立對(duì)應(yīng)關(guān)系

如下圖

首尾被A1占據(jù),從剩下的m-1個(gè)人(A2,A3,...,Am)中選三個(gè)人去站1,2,3這三個(gè)位置,但要求相鄰兩個(gè)位置上的人在“站位”之前不能相鄰．記這三個(gè)人為：O1,O2,O3,并假設(shè)這三個(gè)人的順序如下：

根據(jù)題意特殊位置特殊安排,先確定O1,O3,再確定O2.O1,O3“站位”之前的位置關(guān)系直接影響了O2的取法,而O1,O3均不能與相鄰,O2不與O1,O3相鄰.

問題解答

根據(jù)O1,O3“站位”之前的位置關(guān)系不同,分以下3種情況討論：

(1)O1,O3相鄰.

此時(shí)O1,O3有m-4種取法(從除A1以及與A1相鄰的兩個(gè)人以外的m-3個(gè)人中選兩個(gè)相鄰的人),滿足條件的O2有種m-5取法,故O1,O3相鄰時(shí)傳球方式有種.

(2)O1與O3之間間隔1人.(按較少間隔計(jì))

此時(shí)O1,O3有m-5種取法(從除A1以及與A1相鄰的兩個(gè)人以外的m-3個(gè)人中選兩個(gè)人且這兩人之間間隔為1人),滿足條件的O2有m-6種取法,故O1與O3之間間隔1人時(shí)傳球方式有：A22(m-5)(m-6)種.

(3)O1與O3之間間隔人數(shù)為2人或2人以上.(按較少間隔計(jì))此時(shí)O1,O3有

種取法,滿足條件的O2有m-7種取法,故O1與O3之間間隔人數(shù)為2人或2人以上時(shí)傳球方式有

綜上,不同傳球方式的總數(shù)為：

評(píng)注 本題筆者是以O(shè)1,O3(即第2次傳球和第4次傳球的兩個(gè)人)之間的位置關(guān)系為分類依據(jù),也可以找到其它的分類標(biāo)準(zhǔn),但切記做到“分類不重不漏,分步有理有據(jù)”.由于規(guī)定每次只能把球傳給不相鄰的人且每人至多只傳一次球后情況比較復(fù)雜,用初等方法無法建立傳球方式的總數(shù)關(guān)于傳球次數(shù)的函數(shù)關(guān)系,故本題把傳球次數(shù)具體到4次,當(dāng)然也可以求出傳球5次、6次...的傳球方式的總數(shù),感興趣的讀者可以繼續(xù)往下探索.

圖1

例3 如圖3,7個(gè)人A1,A2,...,A7圍成一圈相互傳球,規(guī)定每次只能把球傳給與自己不相鄰的人,且每人至多只傳一次球.首先由A1發(fā)球作為第一次傳球,經(jīng)過4次傳球,球又回到A1手中,試求所有傳球方式的種數(shù).

解 由題意可知：除了A1之外還有3個(gè)人傳了球,設(shè)這3個(gè)人為O1,O2,O3,且設(shè)傳球次序?yàn)椋篈1→O1→O2→O3→A1,根據(jù)O1,O2,O3這3個(gè)人在圖3中的位置關(guān)系不同,分以下三種情況：

(1)O1,O3相鄰.

此時(shí)O1,O3可能分別是A3,A4、A4,A5、A5,A6或A4,A3、A5,A4、A6,A5,對(duì)于O1,O3的每一種取法,O2都僅有2種可能(例如：O1,O3分別是A3,A4時(shí),O2可能是A6或者A7,其它情況以此類推).故O1,O3相鄰時(shí)有6×2=12種傳球方式.

(2)O1與O3之間間隔1人.(按較少間隔計(jì))

此時(shí)O1,O3可能分別是A3,A5、A4,A6或A5,A3、A6,A4,對(duì)于O1,O3的每一種取法,O2都僅有1種可能(例如：O1,O3分別是A3,A5時(shí),O2可能是A7,其它情況以此類推).故O1,O3之間間隔1人時(shí)有4種傳球方式.

(3)不存在O1與O3之間間隔人數(shù)為2人或2人以上(按較少間隔計(jì))的情況.

綜上,所有傳球方式有16種.

4.感悟

美籍匈牙利數(shù)學(xué)家波利亞說：“如果你不能解決這個(gè)提出的問題,環(huán)視一下四周,找一個(gè)適宜的相關(guān)問題,它可能提供解的方法,解的輪廓,或是提供我們應(yīng)從哪一個(gè)方向著手工作等等.”在碰到新的數(shù)學(xué)問題時(shí),學(xué)生一般都會(huì)有畏難心理,事實(shí)上,難的不是問題本身,而是我們往往被問題的面具嚇到.莫為浮云遮望眼,揭開問題表面的面紗,將新的數(shù)學(xué)問題與已有的知識(shí)結(jié)構(gòu)相聯(lián)系,廣泛聯(lián)想與想象,進(jìn)行發(fā)散思維,通過建立對(duì)應(yīng)關(guān)系,將復(fù)雜問題簡單化、陌生的問題熟悉化、熟悉問題規(guī)律化.學(xué)會(huì)舉一反三,橫向類比,縱向延伸,這樣才能以不變應(yīng)萬變!

[1]羅增儒.從競賽到高考,從染色到傳球[J].中等數(shù)學(xué),2006(10)：18-22.

[2]徐國君.殊途同歸,萬象歸一—再談傳球問題與染色問題[J].中學(xué)數(shù)學(xué)研究,2011(5)：45-46.

[3]G·波利亞.怎樣解題[M].北京：科學(xué)出版社,1982.

*全國教育科學(xué)規(guī)劃教育部重點(diǎn)課題—TPACK視角下卓越教師培養(yǎng)的理論研究與實(shí)踐探索(課題編號(hào)：DHA150287)．