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

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

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

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

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

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

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

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

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

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

(1960－1961年波蘭數學競賽試題)

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

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

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

(1993年全國數學高考試題)

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

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

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

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

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

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

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

(2006年浙江省數學競賽試題)

圖1

圖2

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

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

根據乘法原理可得，符合題意的放法種數共有

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

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

(2008年重慶市數學高考文科試題)

圖3

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

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

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

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

(2010年浙江省數學高考試題)

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

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

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

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

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

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

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

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

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

［2］ 芮玉貴．模式識別解題的理論探討［J］．數學通報，2010(3):45-47．