摸球问题题型及解法【一个投球入盒问题的解法推广】

　　重庆第八中学 400030 　　 　　摘要：本文从研究一个具体的组合问题入手，介绍了隔板法的解题思路，建立了一个关于求解不定方程整数解的数学模型，并运用此模型将问题推广.
　　关键词：投球入盒问题；解法推广；不定方程的解
　　
　　问题 将20个相同的小球放入编号为1，2，3，4的盒子中，要求每个盒内的小球个数不少于它的编号数，有多少种放法？
　　解析先将编号为1，2，3，4的4个盒子中分别放入0，1，2，3个小球后，问题转化为了再向4个盒子分别放小球，要求每个盒子不空，故只需把剩下的14个小球分成四组，每组至少有一个小球，即○○○○○○○○○○○○○○这14个小球中间13个空挡中放入三块隔板，例如○○○|○○○○○|○○○○|○○则对应着编号为1，2，3，4的盒子中依次加入3，5，4，2个球的一种放法，故符合题意的放法总数为C=286种.
　　上述方法即为隔板法，它为上述组合问题建立了一个数学模型，不失为一种好方法，为了揭示这个问题的数学本质，我们将其转化为一类求不定方程的非负整数解或正整数解的个数问题，并将问题推广. 首先提出如下引理：
　　引理1不定方程x1+x2+x3+…+xn=r（r>n，r，n∈N+）的正整数解的个数为C.
　　引理2不定方程x1+x2+x3+…+xn=r（r，n∈N+）的非负整数解的个数为C.
　　证明引理1的不定方程可看作r个相同的球放入n个不同的盒子（r＞n），要求每个盒子不空时球的放法数，于是将r个球排成一行，它们形成r－1个空档，只插n－1个隔板即可符合要求，故有C种方法.
　　引理2的不定方程两边每个xi（i=1，2，…，n）加上1，即为
　　（x1+1）＋（x2+1）+…+（xn+1）=n+r.①
　　令yi=xi+1（i=1，2，…，n），则方程①可化为
　　 y1+y2+…+yn=n+r，②
　　且yi≥1，yi∈N+ .
　　由引理1知不定方程②的正整数解的个数为C=C，从而引理2得证.
　　引理2也可解释为：从n个不同元素中取出r个可重复元素的取法有C.
　　根据上述两个引理，又可得到的另一种解法：
　　设第1，2，3，4号盒子中的球数分别为x，y，z，w. 依题意有
　　x+y+z+w=20且x≥1，y≥2，z≥3，w≥4.
　　令x1=x，x2=y－1，x3=z－2，x4=w－3（xi≥1，xi∈N+，i=1，2，3，4）则问题即方程x1+x2+x3+x4=14有正整数解.
　　由引理1知不定方程的正整数解为C=286.
　　问题的推广情形为：将n个相同的球放入编号为1，2，3，…，m的盒子中（n＞m），要求每个盒子内的球数不少于它的编号数，有多少种放法？
　　将上述问题转化为不定方程x1+x2+…+xm=n满足且xi≥i（i=1，2，…，m）整数解的个数问题，作代换yi=xi－（i－1）（yi≥1且i=1，2，…，m）后，由引理1得不定方程y1+y2+…+ym=n－正整数解的个数为C，于是本题的放法总数为C种.
　　例如在《数学通报》上就有一个组合问题解法的推广情形：
　　在某次数学测验中，学号为（i=1，2，3，…，r）的r位同学的考试成绩f（i）∈｛1，2，…，n-1，n｝，且满足f（1）≤f（2）≤…≤f（r－1）≤f（r），求这r位同学的考试成绩的所有可能情况的种数.
　　此题的数学实质正是从n个不同元素｛1，2，3，…，n｝中取出r个可重复元素的取法数，它与引理2的解的个数是一致的，因此有C种方法.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文