关于竞赛数学中排列组合问题的解题策略

2021-06-08广东省深圳市前海港湾学校518000李可欣

中学数学研究(广东) 2021年9期

广东省深圳市前海港湾学校(518000) 李可欣

从20 世纪60年代华罗庚先生倡导数学竞赛至今,已经过去了50 多年.近年来,为了发掘和培育人才,数学竞赛活动在全世界蓬勃发展,并逐渐形成了一门特殊的数学学科——竞赛数学.竞赛数学介乎于中小学与大学教学之间,不断推陈出新,发掘新问题、新方法、新结果,将现代化的内容与趣味性的问题有机结合,把普遍性的问题与独创性的技巧有机结合,在展现数学魅力的同时,利用自己所处的位置,大量地、方便地吸收最前沿的成果,大力开发同学们的数学思维,培养同学们的数学兴趣.而排列组合是高中数学人教版选修2-3 的内容,隶属组合数学,是高中数学学习的一个重难点,作为引申,在各类高中数学竞赛中也常见其身影.本文将归纳出解决竞赛数学中的排列组合问题常用的两种解法.

下面我们结合例题对排列组合解题常用的分类讨论、构造不定方程及利用递推关系三种解题策略进行展开.

1 分类讨论

分类讨论的关键在于如何分类及具体分几类,根据不同的分类方法一道题目可以有许多不同的解法.

例1 在0 和10000 之间有多少个整数恰好有一位数字是5?

令S为0 和10000 之间恰好有一位数字是5 的整数的集合.

解法一我们对S做如下划分:S1是S中的一位数的集合,S2是S中的两位数的集合,S3是S中的三位数的集合,S4是S中的四位数的集合.S中没有五位数.显然,我们有|S1|=1.S2的数很自然地分成两种类型:

(1)个位数字是5,(2)十位数字是5.

个位数字是5 的数一共有8 个(十位数字既不能是0 也不能是5),十位数字是5 的数一共有9 个(个位数字不能是5).故|S2|= 8 + 9 = 17.用类似的推理我们得到|S3|= 8·9 + 8·9 + 9·9 = 225.以及|S4|= 8·9·9 + 8·9·9 + 8·9·9 + 9·9·9 = 2673.因此,|S|=1+17+225+2673=2916.

解法二通过添加前导零(如6 看作0006,25 看作0025,352 看作0352),可以把S中的每一个数都当作4 位数.现在我们根据数字5 是位于第一位、第二位、第三位还是第四位而把S划分成S′1,S′2,S′3,S′4,其中S′i表示数字5 处于第i位的集合(i= 1,2,3,4).这四个集合中的每一个都含有9·9·9 = 729 个整数,从而S所含整数的数目等于4·729=2916.

例2(第一届美国数学邀请赛第7 题)某个国王的二十五位骑士围坐在他们的圆桌旁,他们中间的三位被选派去杀一条恶龙(设三次挑选都是等可能的),令P是被挑到的三位骑士中至少有两位是邻座的概率.若把P写成一个既约分数,其分子与分母之和是多少?

解法一显然,在25 位骑士中任选3 位的选法总共有=2300 种,又根据在三位骑士中至少有两位是邻座的条件,可分出两种情况.

一、三位骑士依次相邻,那么有25 种选法;二、两位骑士是邻座,但第三位骑士不选在已经邻座的两位骑士的两旁,也就是说,第三位骑士只能在剩下的21 位中任选一位,这样有25×21 = 525 种选法.因此,满足条件的基本事件数为25+525=550.所以P=分子分母之和为57.

解法二同解法一,在25 位骑士中任选3 位的选法总共有=2300.由于25 位骑士围坐在圆桌旁,取相邻两位骑士的取法有25 种,那么取第三位的取法就有23 种.也就说,被挑到的三位骑士中有两位是邻座的取法有25·23 = 575种.然而,相邻三位骑士的25 种取法被取了两次,所以被挑到的三位骑士中至少有两位是邻座的取法有575−25=550种.因此P=分子分母之和为57.

解法三先从围坐的25 人选一人,则有25 种可能性,并始终约定被选中的人的右边(或左边) 那个人也随同而去.如此,已选得相邻两人,再在余下的人中选一个即可.为避免重复,在与已选两人不相邻的21 人中选一人,有21 种选法,然后加上已选两人之右邻(或左邻)的一人的一种,计得+1=22 种选法,故满足条件的选法有25·22=550 种.于是P=分子分母之和为57.

例3(第一届美国数学邀请赛第10 题)数1447,1005 和1231 有某些共同点,即每一个都是以1 开头的四位数,且每个数恰好有两个数字相等.这样的数共有多少个?

解法一首先,不难发现满足条件的四位数有六种类型:11AB,1A1B,1AB1,1AAB,1ABB,1ABA.而对于每一类A都有9 种可能,B都有8 种可能,所以这样的数共有6·9·8=432 个.

解法二考虑以1 开头的四位数的后三位数,分两种情况.若后三位数中含有数字1,那么1 放置的位置有3 种可能,剩下两位数中一位有9 种可能性,另一位只有8 种可能,根据乘法原理,这样的数有3·8·9 = 216 个;若后三位数字中不含1,则其中相同的两位数字的位置可能有3 种,而该数字有9 种可能,剩下一位数字仅有8 种可能,故共有216 种可能.因此这样的数总共有216+216=432 个.

从以上三个例题,我们不难发现,一道题目往往可以从许多不同的角度去分类讨论,而难易度也不尽相同.因此我们不止要学会如何分类讨论,还要选取精准的角度,让分类尽量简洁.

2 构造不定方程

首先我们了解什么是“隔板法”.

隔板法就是在n个元素中的(n −1) 个空中放置m(0 ≤m≤n −1) 个隔板,从而把n个元素分成m+1组的方法.需要注意的是:(1)n个元素互异;(2)隔开的每一组中至少有一个元素;(3)分开的组彼此相异.结合例4 进行进一步理解.

例4求方程x+y+z=10 的正整数解的个数.

解析方程x+y+z=10 可以看成是用2 个隔板插入10 个并列的圆球中,从而把10 个圆球分为3 组,又因为条件要求解为正整数,所以每两个隔板之间必须有至少一个球,如○○丨○○○丨○○○○○.那么容易看出,每一种隔板的放置方法,对应的就是方程的一组解.因此方程x+y+z=10 的正整数解有=36 个.

与例4 相似,我们可以利用隔板法得到

引理不定方程x1+x2+···+xm=n(m≤2,n≤2,m≤n)的正整数解有组.

推论不定方程x1+x2+···+xm=n(m≤2,n≤2,m≤n)的非负整数解有组.

接下来,跟住以上的引理和推论,我们可以构造不定方程解决竞赛中的一些排列组合题.

例5(1990年全国高中数学联赛)8 个女孩和25 个男孩围成一圈,任意两个女孩之间至少站两个男孩.问:共有多少种不同的排列方法(只要把圈旋转一下就重合的排法认为是相同的)?

解析先考虑8 个女孩围成一圈,则有=7!种不同的排列,其中8 个女孩中的7 个空要排入25 个男孩,不妨设每一个空中的男孩数分别为x1,x2,··· ,x8,且x1+x2+···+x8= 25.由于条件要求任意两个女孩之间至少站两个男孩,故上述不定方程有限制条件x1≤2,x2≤2,··· ,xn≤2.将不定方程化为(x1−1)+(x2−1)+···+(x8−1) = 17,再令y1=x1−1,y2=x2−1,··· ,y2=x8−1,即得y1+y2+···+y8= 17,且yi≤1(其中1 ≤i≤8).于是上述问题就转化为以上不定方程的正整数解的组数.由引理知其正整数解个数为.

由因为25 个男孩有25!种排列,所以符合条件的排列方法有7!25!种.

例6(1989年全国高中数学联赛)从数1,2,··· ,14 中按由小到大的顺序取出a1,a2,a3,使得同时满足a2−a1≤3与a3−a2≤3.则所有符合要求的不同取法有多少种?

解析首先由条件知a1≤1,a2−a1≤3,a3−a2≤3,a3≤ 14,令a1=x1,a2−a1=x2,a3−a2=x3,14−a3=x4,则x1+x2+x3+x4=14.于是问题转化为求不定方程x1+x2+···+x8=14 在条件x1≤1,x2≤3,x3≤3,x4≤0 下的整数解的组数.

将方程转化为x1+(x2−2)+(x3−2)+(x4+1)=11.令y1=x1,y2=x2−2,y3=x3−2,y4=x4+1,即得y1+y2+y3+y4=11,且yi≤1(其中1 ≤i≤4).由引理知y1+y2+y3+y4= 11 的正整数解的组数是= 120 个,所以符合要求的不同取法有120 种.

通过以上的三个例子,可以发现根据题目的条件列出不定方程是解题的突破口,而在列出不定方程后,要不断利用换元法,使方程转化为满足每一个未知数都≤1 或都≤0 的不定方程,再根据引理或推论得到其正整数解的个数,从而得出答案.下面,我们来解析一道难度较大的排列组合题.

例7(2002年全国高中数学联赛)在世界杯足球赛前,F国教练为了考察A1,A2,··· ,A7这七名队员,准备让他们在三场训练比赛(每场90 分钟)中均上场.假设在比赛的任何时刻,这些队员中有且仅有一人在场上,且A1,A2,A3,A4每人上场的总时间(以分钟为单位)均能被7 整除,A5,A6,A7每人上场的总时间(以分钟为单位)均能被13 整除.若每场换人次数不限,则按每名队员上场的总时间计算,共有多少种不同的情形?

解析设第i名队员上场的时间为xi分钟(1 =1,2,···7),问题即求不定方程x1+x2+···+x7= 270在条件7| xi(1 ≤i≤4)且13| xj(5 ≤j≤7)下的正整数解的组数.

若(x1,x2,··· ,x7)是满足不定方程x1+x2+···+x7=270 的一组正整数解,则应有x1+x2+x3+x4= 7m及x5+x6+x7= 13n,其中m,n是正整数.因此,m,n是不定方程7m+ 13n= 270 在条件m≤4 且n≤3 下的一组正整数解.而不定方程7m+ 13n= 270 可以转化为7(m −4)+13(n −3) = 203,令m′=m −4,n′=n −3(m′≤0,n′≤0),则上述方程化为7m′+13n′= 203,也就是说,问题转化为求不定方程7m′+13n′=203 的非负整数解.

易观察到7·2+13·(−1) = 1,可推出7·406+13·(−203) = 203,即m0= 406,n0=−203 是7m′+13n′=203 的整数特解,从而求得其整数通解为m′= 406−13k,n′=−203+7k,其中k是整数.

由于m′≤0,n′≤0,解得129 ≤k≤31.分别取k=29,30,31 得到不定方程7m′+13n′=203 满足条件的三组非负整数解从而满足不定方程7m+13n=270 在条件m≤4 且n≤3 下的三组正整数解是

①在m= 33,n= 3 时,显然x5=x6=x7= 13 仅有一种可能; 又设xi= 7yi(i= 1,2,3,4),则由不定方程y1+y2+y3+y4= 33 有= 4960 组正整数解.即此时不定方程x1+x2+···+x7=270 有3 有=4960 组正整数解.

②在m= 20,n= 10 时,设xi= 7yi(i= 1,2,3,4),xj=13yj(i=5,6,7),则由不定方程y1+y2+y3+y4=20有组正整数解以及y5+y6+y7=10 有组正整数解.此时不定方程x1+x2+···+x7=270 有=34884组正整数解.

③在m= 7,n= 17 时,仍设xi= 7yi(i=1,2,3,4),xj= 13yj(j= 5,6,7),则由不定方程y1+y2+y3+y4=7 有组正整数解以及y5+y6+y7=17 有组正整数解.此时不定方程有=2400 组正整数解.

综上,满足条件的正整数解的组数有4960+34884+2400=42244 个,即满足题意的不同情形有42244 种.

3 利用递推关系

利用递推关系,就是要找到问题一般的关系式,即递推关系式来解决具体问题,而寻找递推关系式,往往可以从简单的问题入手.

首先我们介绍一个经典的递推数列,即斐波那契数列,以下为其提出的问题.

在一年的伊始,把新近出生的雌雄一对兔子放进一个笼子里.从第二个月开始,每个月这个雌兔子生出雌雄一对兔子.而每对新出生的雌雄兔子也从第二个月开始每个月生出一对雌雄兔子.确定一年后笼子里有多少兔子?

不妨设fn为第n个月笼子里兔子的对数.不难发现,f1=1,f2=1,f3=2,f4=3,f5=5,f6=8,f7=13,f8=21,f9= 34,f10= 55,f11= 89,f12= 144,f13= 233,因此一年之后笼子里有233 只兔子,并且可以看出fn的递推关系式fn=fn−1+fn−2(n≤2),加入初始条件f0= 0,f1= 1,则满足这个递推关系式及初始条件的数列叫做斐波那契数列.

利用递推关系解排列组合问题,常与斐波那契数列有关.

例810 个信封只放A/B,则有210= 1024 种可能,除去连续AAA或BBB的可能,还有几种可能?

解法一除去连续AAA或BBB的可能,即任意三个信封中至多只有两个相同的A或B相邻,则只有六种可能AAB,ABA,ABB,BAB,BBA,BAA,用树状图列出前三个信封为AAB与ABB的可能性.

首先,从图1 容易看出,AABABA,AABAAB,AABBAB满足条件的可能性相同,都有8种,而AABBAA,AABABB都有5 种可能性,也就是说,若前三个信封放置的是AAB,那么除去连续AAA或BBB的可能,有3·8+5·2=34 种可能性.而从图2 可以看出,前三个信封为ABB时,有5+8+8=21 种可能性.继续利用列举法,不难发现前三封信封为AAB,ABA,BBA,BAB的可能性相同,即34·4 = 136 种;前三封信封为ABB,BAA的可能性相同,即21·2=42 种.因此除去连续AAA或BBB的可能,还有136+42=178 种可能.

图1

图2

解法二设fn为n个信封中只放A/B且除去连续AAA或BBB的可能性.可以列出如下树状图(图3).可以看出f1= 1,f2= 2,f3= 3,f4= 5,f5= 8··· ,并且满足递推关系式fn=fn−1+fn−2(n≤2),构成了一个斐波那契数列.继续算下去,f6=13,f7=21,f8=34,f9=55,f10=f9+f8= 34+55 = 89,也就是说以A开头的10 个信封只放A/B且除去连续AAA或BBB的可能性有89 种.同理以B开头的可能性也有89 种,因此一共有89+89=178 种可能.