节点文献
隔板显奇效 巧解计数题
【关键词】 计数;隔板;
【正文】问题:求不定方程x1+x2+x3+3x4+3x5+5x6=21的正整数解的组数。
这是2009年全国高中数学联合竞赛湖北省预赛第10题,一个计数问题。如何解答这一问题,涉及一类计数问题的解答,这类问题就是无差异的数据分配问题。
无差异的数据分配问题,就是分配给对象的元素仅有数据多少的不同,不管元素自身的差异。比如,9个优秀指标分配给四个部门,每个部门至少一个,就是无差异数据分配。
无差异的数据分配问题可以利用隔板法进行求解。我们先来研究一个简单案例,感受隔板奇效。
案例1:将10朵鲜花全部插到四个花瓶里,每瓶至少一朵,有多少种插法。
分析:每个花瓶插入数目不同,插法就不同,至于具体插哪朵,没有影响,因此为无差异数据分配问题。如图所示,将10朵鲜花排成一列,
○○○○○○○○○○
10朵花之间有9个空,选三个空各放一块隔板,就对应一种数据分配方法,比如,
○○l○○○l○○l○○○
意味着四个花瓶依次插2、3、2、3朵。换一种隔法,
○l○○○○l○○l○○○
意味着四个花瓶依次插1、4、2、3朵。
从9个空中选3个放隔板的选法数,就对应着不同的插花方法数,共有种。
注意,上面采用隔板法时,要求每个对象至少分一个元素。下面给出两个变化形式,供大家进一步体会方法。
案例2:将10朵鲜花全部插到四个花瓶里,有多少种插法。
分析:与案例1比较,这里插花时的要求由“每瓶至少一朵”变为无要求,意味着有花瓶可以是空的。直接用案例1的做法,不能达到要求。如何将无要求转化为“每瓶至少一朵”,是解题的关键。我们不妨先在花的总数中加上瓶数,使鲜花总数成为14,按案例1的方法,每瓶至少分一朵,分完后每瓶再减去一朵,就是一种实际的分配方法。比如按14朵分成1、1、6、6,实际分就是0、0、5、5。由案例1方法,14朵花全部插入4个花瓶中,每瓶至少一朵,有种插法,所以案例2插法种数为。
案例3:将10枝玫瑰全部插到编号为1、2、3的三个花瓶里,每瓶所插花数不低于花瓶编号,有多少种插法。
分析:与案例1比较,这里插花时的要求由“每瓶至少一朵”变为“每瓶所插花数不低于花瓶编号”,直接用案例1的做法,也不能达到要求。如何将“每瓶所插花数不低于花瓶编号”转化为“每瓶至少一朵”,是解题关键。我们可以先在编号为2的花瓶中先插1枝,编号为3的花瓶中先插2枝,剩下的7朵花插到3个花瓶中每瓶至少一朵,就可以利用案例1的方法,7朵花之间有6个空,从6个空中选2个放入隔板,共有种放法。
如果我们将案例中的插花变为求方程的正整数解或求方程的整数解,就分别对应着案例1与案例2的解答方式。
下面给出文章开头竞赛题的解答,供大家参考。
解答 :令x1+x2+x3=x,x4+x5=y,x6=z,则x≥3,y≥2,z≥1.
先考虑不定方程x+3y+5z=21满足x≥3,y≥2,z≥1的正整数解.
∵x≥3,y≥2,z≥1,
∴5z=21-x-3y≤12
∴1≤z≤2,
当z=1时,有x+3y=16,
此方程满足x≥3,y≥2的正整数解为(x,y)=(10,2),(7,3),(4,4).
当z=2时,有x+3y=11,此方程满足x≥3,y≥2的正整数解为(x,y)=(5,2).
所以不定方程x+3y+5z=21满足x≥3,y≥2,z≥1的正整数解为(x,y,z)=(10,2,1),(7,3,1)(4,4,1),(5,2,2)
又方程x1+x2+x3=x(x∈N,x≥3)的正整数解的组数为C2x-1,方程x4+x5=y(x∈N,x≥2)的正整数解的组数为C1y-1,故由分步计数原理知,原不定方程的正整数解的组数为
C29C11+C26C12+C23C13+C24C11=36+30+9+6=81。
链接练习:
1.将10个保送生预选指标分配给某重点中学高三年级六个班,每班至少一名,共有多少种分配方案?
2.求方程x1+x2+x3+x4=100的自然数解的组数.
参考答案
1.解:将10个名额并成一排,名额之间有9个空,用5块隔板插入9个空,就可将10个名额分为6部分,每一种插法对应一种分配方法,故有C59种方案.
2.解:将原方程变为(x1+1)+(x2+1)+(x3+1)+(x4+1)=104,
令yi=xi+1,(i=1,2,3,4),求方程x1+x2+x3+x4=100的自然数解,相当于求方程y1+y2+y3+y4=104的正整数解的个数,用隔板法,共有C3103组解法.
这是2009年全国高中数学联合竞赛湖北省预赛第10题,一个计数问题。如何解答这一问题,涉及一类计数问题的解答,这类问题就是无差异的数据分配问题。
无差异的数据分配问题,就是分配给对象的元素仅有数据多少的不同,不管元素自身的差异。比如,9个优秀指标分配给四个部门,每个部门至少一个,就是无差异数据分配。
无差异的数据分配问题可以利用隔板法进行求解。我们先来研究一个简单案例,感受隔板奇效。
案例1:将10朵鲜花全部插到四个花瓶里,每瓶至少一朵,有多少种插法。
分析:每个花瓶插入数目不同,插法就不同,至于具体插哪朵,没有影响,因此为无差异数据分配问题。如图所示,将10朵鲜花排成一列,
○○○○○○○○○○
10朵花之间有9个空,选三个空各放一块隔板,就对应一种数据分配方法,比如,
○○l○○○l○○l○○○
意味着四个花瓶依次插2、3、2、3朵。换一种隔法,
○l○○○○l○○l○○○
意味着四个花瓶依次插1、4、2、3朵。
从9个空中选3个放隔板的选法数,就对应着不同的插花方法数,共有种。
注意,上面采用隔板法时,要求每个对象至少分一个元素。下面给出两个变化形式,供大家进一步体会方法。
案例2:将10朵鲜花全部插到四个花瓶里,有多少种插法。
分析:与案例1比较,这里插花时的要求由“每瓶至少一朵”变为无要求,意味着有花瓶可以是空的。直接用案例1的做法,不能达到要求。如何将无要求转化为“每瓶至少一朵”,是解题的关键。我们不妨先在花的总数中加上瓶数,使鲜花总数成为14,按案例1的方法,每瓶至少分一朵,分完后每瓶再减去一朵,就是一种实际的分配方法。比如按14朵分成1、1、6、6,实际分就是0、0、5、5。由案例1方法,14朵花全部插入4个花瓶中,每瓶至少一朵,有种插法,所以案例2插法种数为。
案例3:将10枝玫瑰全部插到编号为1、2、3的三个花瓶里,每瓶所插花数不低于花瓶编号,有多少种插法。
分析:与案例1比较,这里插花时的要求由“每瓶至少一朵”变为“每瓶所插花数不低于花瓶编号”,直接用案例1的做法,也不能达到要求。如何将“每瓶所插花数不低于花瓶编号”转化为“每瓶至少一朵”,是解题关键。我们可以先在编号为2的花瓶中先插1枝,编号为3的花瓶中先插2枝,剩下的7朵花插到3个花瓶中每瓶至少一朵,就可以利用案例1的方法,7朵花之间有6个空,从6个空中选2个放入隔板,共有种放法。
如果我们将案例中的插花变为求方程的正整数解或求方程的整数解,就分别对应着案例1与案例2的解答方式。
下面给出文章开头竞赛题的解答,供大家参考。
解答 :令x1+x2+x3=x,x4+x5=y,x6=z,则x≥3,y≥2,z≥1.
先考虑不定方程x+3y+5z=21满足x≥3,y≥2,z≥1的正整数解.
∵x≥3,y≥2,z≥1,
∴5z=21-x-3y≤12
∴1≤z≤2,
当z=1时,有x+3y=16,
此方程满足x≥3,y≥2的正整数解为(x,y)=(10,2),(7,3),(4,4).
当z=2时,有x+3y=11,此方程满足x≥3,y≥2的正整数解为(x,y)=(5,2).
所以不定方程x+3y+5z=21满足x≥3,y≥2,z≥1的正整数解为(x,y,z)=(10,2,1),(7,3,1)(4,4,1),(5,2,2)
又方程x1+x2+x3=x(x∈N,x≥3)的正整数解的组数为C2x-1,方程x4+x5=y(x∈N,x≥2)的正整数解的组数为C1y-1,故由分步计数原理知,原不定方程的正整数解的组数为
C29C11+C26C12+C23C13+C24C11=36+30+9+6=81。
链接练习:
1.将10个保送生预选指标分配给某重点中学高三年级六个班,每班至少一名,共有多少种分配方案?
2.求方程x1+x2+x3+x4=100的自然数解的组数.
参考答案
1.解:将10个名额并成一排,名额之间有9个空,用5块隔板插入9个空,就可将10个名额分为6部分,每一种插法对应一种分配方法,故有C59种方案.
2.解:将原方程变为(x1+1)+(x2+1)+(x3+1)+(x4+1)=104,
令yi=xi+1,(i=1,2,3,4),求方程x1+x2+x3+x4=100的自然数解,相当于求方程y1+y2+y3+y4=104的正整数解的个数,用隔板法,共有C3103组解法.
- 【发布时间】2018/10/10 9:59:27
- 【点击频次】308