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

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

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

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

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

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

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

1.題型一?染色問題

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

圖1

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

我們將此問題與“染色問題”建立對應(yīng)關(guān)系.如果把從A1開始傳球最后回到A1手中每個環(huán)節(jié)的人員按照傳球次序順次放入圖1中對應(yīng)的n個區(qū)域O1,O2,...,On(n≥3), (其中起始的A1和結(jié)束的A1都放入O1區(qū)域),由于持球人不能把球傳給自己,故相鄰兩區(qū)域的人員不同,那么問題本質(zhì)就是：用m(m≥3)種顏色A1,A2,...,Am給圖1中的n(n≥3)個區(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同色的情形,此時可將O1與On視為同一個區(qū)域,這樣的染法恰為an-1種,因此我們得出：

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

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

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

圖2

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

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

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

2.題型二?動點問題

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

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

我們規(guī)定傳球過程中順時針傳球為正向,逆時針傳球為負向,設(shè)n次傳球中有x次正向傳球,n-x次負向傳球.

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

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

(1)A1所在位置相當于數(shù)軸原點;

(2)n次傳球?qū)?yīng)動點的n次運動,順時針傳球一次相當于點向右運動一個單位,逆時針傳球一次相當于點向左運動一個單位;

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

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

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

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

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

(4)點的每一種運動方式對于一種傳球方式.

問題解答

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

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

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

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

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

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

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

3.題型三?站位問題

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

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

如下圖

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

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

問題解答

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

(1)O1,O3相鄰.

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

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

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

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

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

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

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

圖1

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

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

(1)O1,O3相鄰.

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

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

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

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

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

4.感悟

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

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

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

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

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