●甘大旺 (北侖明港中學(xué) 浙江寧波 315806)

從競賽到高考的裝錯信箋題及變式題探究

●甘大旺 (北侖明港中學(xué) 浙江寧波 315806)

瑞士數(shù)學(xué)家伯努利提出了裝錯信箋問題——某人寫了n(n∈N+)封不同的信，并在n個信封上寫下對應(yīng)的地址，問:把所有信箋全部裝錯的方法共有多少種?

后來，著名數(shù)學(xué)家歐拉認為此題是“組合理論的一道妙題”，并運用遞推數(shù)列{xn}獨立地解決了這道妙題，求出的方法種數(shù)用階乘表示為

歐拉解法的關(guān)鍵是找出遞推數(shù)列的遞推式xn+2=(n－1)(xn+1+xn)，難點是后續(xù)的求通項．下面筆者另辟蹊徑，運用容斥原理驗證式(1)．

證明當(dāng)正整數(shù)n≥2時，將這n封信箋任意裝入這n個信封，不管裝對裝錯，共有n!種方法．其中，至少有1封信箋恰好正確裝入信封的任意裝法有·(n－1)!種;至少有2封信箋恰好正確裝入信封的任意裝法有·(n－2)!種;至少有3封信箋恰好正確裝入信封的任意裝法共有·(n－3)!種;…;至少有n－1封信箋恰好正確裝入信封的裝法共有·1!種，因此所有n封信箋都正確裝入信封的裝法共有種．根據(jù)容斥原理知，符合題意的投放信箋方法種數(shù)共有

伯努利—歐拉裝錯信箋的經(jīng)典問題，有時呈現(xiàn)特例、有時變換情景、有時變換目標，活躍在數(shù)學(xué)競賽題和高考題中．對于這類直白或翻新的經(jīng)典問題，假如能自覺運用上述結(jié)論(2)，就可以輕松、快捷、愉悅地解決，并培養(yǎng)模式識別、等價變換的數(shù)學(xué)思想．

例1某人給6個不同的收信人寫了6封信，并且分別寫好了6個信封，問有多少種投放信箋方法使得信箋和收信人皆不相符?

(1960－1961年波蘭數(shù)學(xué)競賽試題)

解在伯努利—歐拉裝錯信箋問題中，取n=6，直接運用結(jié)論可知，共有種投放信箋方法，使得信箋和收信人皆不相符．

評注此題是伯努利—歐拉裝錯信箋問題當(dāng)n=6時的特例，沿用了經(jīng)典問題的情景．

例2將數(shù)字1，2，3，4填入標號為1，2，3，4的4個方格里，每格填1個數(shù)字，則每個方格的標號與所填的數(shù)字均不相同的填法有＿ 種．

(1993年全國數(shù)學(xué)高考試題)

解對應(yīng)于伯努利—歐拉裝錯信箋問題，取n=4，則每個方格的標號與所填的數(shù)字均不相同的填法有－+1=12－4+1=9種．

評注此題變換了伯努利—歐拉裝錯信箋問題的情境，數(shù)字1，2，3，4對應(yīng)著信箋，標號為1，2，3，4的4個方格對應(yīng)著信封．

例34封不同信件放入4只寫好地址的信封中，全裝錯的概率為 ．

(2005年上海交通大學(xué)自主招生試題)

解4封不同信件放入4只寫好地址的信封中，任意放入的方法共有4!種，其中全裝錯的方法有－+1種，因此全裝錯的概率為

評注此題保持了伯努利——歐拉裝錯信箋問題的情境，但把解題目標變換為求概率．

例4把5枚無區(qū)別的棋子放在5×5小方格中(如圖1)，每行每列放且僅放1枚棋子，不允許放在黑色小方格內(nèi)，則共有＿＿ 種放法．

(2006年浙江省數(shù)學(xué)競賽試題)

圖1

圖2

解第1步，先構(gòu)造如圖2所示的5×5小方格，其中把第 k行第 k列(k=1，2，3，4，5)的小方格染成黑色，現(xiàn)在把5枚無區(qū)別的棋子放在這個新5×5小方格中，每行每列放且僅放1枚棋子，不允許放在黑色小方格內(nèi)(即第k行第k列不放棋子)，這與伯努利—歐拉裝錯信箋問題當(dāng)n=5時的情形同構(gòu)，此時有－+－1種放棋子方法．

第2步，將上述構(gòu)造的5×5小方格的第1列與第2列全部對調(diào)、第4列與第5列全部對調(diào)，就回歸了題意，此時只有1種固定的方法．

根據(jù)乘法原理可得，符合題意的放法種數(shù)共有

評注一般地，設(shè) A={a1，a2，a3，…，an}，{b1，b2，b3，…，bm}，其中正整數(shù) n≥2，根據(jù)集合中元素的無序性可能交換B中元素的位置，可得B={bk1，bk2，bk3，…bkn}．在由A到B的一一映射f:A→B中，若不允許所有的am與akm(m=1，2，3，…，n)相對應(yīng)，則這種一一映射的個數(shù)共有

例5某人有3種顏色的燈泡(每種顏色的燈泡足夠多)，要在如圖3所示的6個點A，B，C，A1，B1，C1上各安裝一個燈泡，要求同一條線段2端的燈泡不同色，則不同的安裝方法共有＿＿ 種．

(2008年重慶市數(shù)學(xué)高考文科試題)

圖3

解第1步，在A，B，C處各安裝一個燈泡，要求用到3種顏色的燈泡各1個，有種方法;

第2步，在A1，B1，C1處各安裝一個燈泡，也用到上述3種顏色的燈泡各1個，還要求A與A1，B與B1，C與C1處的燈泡都不同色，這與伯努利—歐拉裝錯信箋問題當(dāng)n=3時同構(gòu)，此時有－1種安裝方法．

評注這道高考題的情景設(shè)置貼近實際，與2008年全國數(shù)學(xué)高考文科試題Ⅰ第12題有異曲同工之妙．解答過程中第2步的本質(zhì)與伯努利—歐拉裝錯信箋問題相吻合．

例6有4位同學(xué)在同一天的上、下午參加“身高與體重”、“立定跳遠”、“肺活量”、“握力”、“臺階”5個項目的測試，每位同學(xué)上、下午各測試一個項目，且不重復(fù)．若上午不測“握力”項目，下午不測“臺階”項目，其余項目上、下午都各測試一人，則不同的安排方法共有 種(用數(shù)字作答)．

(2010年浙江省數(shù)學(xué)高考試題)

解為方便敘述，把題設(shè)的4位同學(xué)分別記為甲、乙、丙、丁，把“身高與體重”、“立定跳遠”、“肺活量”、“握力”、“臺階”等5 個項目依次記為 A，B，C，D，d．依題意，上午安排 A，B，C，d 各一項，下午安排 A，B，C，D各一項，且同一人的上、下午不能同測．

第1步，給甲、乙、丙、丁安排上午的A，B，C，d項目，此時有種方法．

第2步，給上午測試、項目的同學(xué)安排下午的測試項目，分2小類:

(1)當(dāng)D與d安排給同一人時，下午的A，B，C項目不能與上午的此項目安排給同一人，這與伯努利—歐拉裝錯信箋問題當(dāng)n=3時的情形同構(gòu)，此時有－1種方法;

(2)當(dāng)D與d不安排給同一人時，把與d視為同類，把A，B，C與自身視為同類，則下午的A，B，C，D不能與上午的同類項目安排給同一人，這與伯努利—歐拉裝錯信箋問題當(dāng)n=4時的情形同構(gòu)，此時有－+1種方法．

根據(jù)乘法原理和加法原理，得不同的安排方法共有

評注這里運用伯努利—歐拉裝錯信箋問題解題，有2點創(chuàng)新:一是局部運用此經(jīng)典問題;二是把此經(jīng)典問題中的相同元素不重復(fù)情形恰當(dāng)拓寬為同類元素不重復(fù)．

綜上所述，伯努利—歐拉裝錯信箋問題較早出現(xiàn)在競賽題中，隨后活躍在數(shù)學(xué)高考題和競賽題中．由此看來，探究在數(shù)學(xué)高考大綱與數(shù)學(xué)競賽大綱公共范圍內(nèi)的競賽題，是高考數(shù)學(xué)的命題研究、解題研究的新途徑．

［1］ 鄭國榮．高中生數(shù)學(xué)辭海［M］．上海:上海人民出版社，2001．

［2］ 芮玉貴．模式識別解題的理論探討［J］．?dāng)?shù)學(xué)通報，2010(3):45-47．