旗杆上挂旗帜,一道美国数学赛试题的多种解法

橘子网 2,102 0

旗杆上挂旗帜的方法,这道题源自2008年美国数学邀请赛(AIME),原题如下:

There are two distinguishable flagpoles, and there are 19 flags, of which 10 are identical blue flags, and 9are identical green flags. Let N be the number of distinguishable arrangements using all of the flags in which each flagpole has at least one flag and no two green flags on either pole are adjacent. Find the remainder when is divided by 1000.

翻译成中文:有两根不同的旗杆和19面旗帜,其中10面完全相同的蓝旗,9面完全相同的绿旗。现在要将所有的旗帜都挂到这两根旗杆上,使得每根旗杆上至少有一面旗帜,并且任意两面绿旗都互不相邻。设不同的排列数目为N,求N除以1000后的余数。

旗杆上挂旗帜,一道美国数学赛试题的多种解法

与大部分的美国数学竞赛题类似,这道题目看上去似乎很容易,但事实上却不是那么轻易可以得到答案。读者朋友们可以先尝试着自己去解一下,然后再看下文的答案。

既然我认为有点意思,那么这道题通常是可以用不同的方法去解答的,解题思路殊途同归的题目才值得思考。下面我就用不同的方法去解答这道题目。

解法1:

为了说明方便,先给两根旗杆标为1号旗杆和2号旗杆。设Gn表示在1号旗杆上有n面绿旗的排列数。

假如其中一根旗杆挂上了所有的绿旗,为了保证任意两面绿旗都互不相邻,则这根旗杆上将至少挂8面蓝旗以作为任意两面绿旗的间隔;根据题意,我们还要确保2号旗杆上至少挂一面蓝旗;那么,最后剩下的一面蓝旗可以挂在10+1=11个位置上。于是我们可以得到:G0G9=11。

同理可以推出,假如当0<n<9时,则1号旗杆上挂有n面绿旗,同时至少还要确保n-1面蓝旗来进行间隔;相应地,2号旗杆上就挂有9-n面绿旗,同时至少有8-n面蓝旗。这里需要展开一下:当n=1时,1号旗杆上挂有1面绿旗,2号旗杆上会有8面绿旗;当n=2时,1号旗杆上挂有2面绿旗,2号旗杆上会有7面绿旗;n=3时,1号旗杆上挂有3面绿旗,2号旗杆上会有6面绿旗;……。无论n如何变化,我们都可以确定有7面蓝旗是被绿旗锁定了。那么,剩下的蓝旗就可以在(n+1)+(10-n)=11个位置中任意选择并可重复。于是,这个问题就相当于是从13个位置中选3个,因此剩下的3面蓝旗可能的排列数就是C(13,3)。

稍作停顿,说明一下,这里我估计有一些读者可能会理解不了。是的,没有打错,不是11,是13;因为11个位置中都可以重复放入剩余3面蓝旗中的任意一面,所以是用10个隔板将3面蓝旗相隔开来。

因而,全部的排列数为:2×11+8×C(13,3)=2310;最后的答案就是310。

解法2:

假如现在不是两根旗杆,而是一根旗杆,那么10面蓝旗和9面绿旗挂在这根旗杆上,如何才能保证任意两面绿旗都互不相邻呢?这个问题就相当于是要在10面蓝旗所构成的11个空位上选9个位置放绿旗的问题了。

然后,我们把这根旗杆一分为二,变成两根旗杆,就是我们题目所描述的情况了。但这里似乎忽视了一种情况,即第一根旗杆可能会以绿旗结束,同时第二根旗杆可能会以绿旗开始。这种情况符合题意,但在一根旗杆上是不被允许的。为了解决这个困扰,我们可以额外增加一面蓝旗作为分隔。因此,前面一根旗杆的情况就变为了在11面蓝旗所构成的12个空位上选9个位置放绿旗的问题了,即C(12,9)。又因为这11面蓝旗都可以作为两根旗杆一分为二的间隔,所以总共有11×C(12,9)=2420种排列方式。

但是,上面的计算中其实还包含了极端情况,就是所有的旗帜都在一根旗杆上的情况。由于两根旗杆是不同的,所以不符合题意的情况有2×C(11,9)=110种。

因此,综合起来就是N=11×C(12,9)-2×C(11,9)=2420-110=2310种。

解法3:

这种解法源自一位读者朋友提出,是在解法2的基础上进行变化思考。这个解法的要点是这里不用额外的蓝旗去作为分隔,考虑让蓝旗和绿旗排成一行,中间任选一个位置分成两部分,分别挂到2根旗杆上。为了满足题目要求,可以分两种情况讨论。情况19面绿旗之间都有蓝旗分隔。情况2:只存在2面绿旗相邻,但恰好从这2面绿旗之间进行分割,分别挂到不同的旗杆上去。

对于情况19面绿旗必定会锁定8面蓝旗,剩余2面蓝旗,9面绿旗看作9个隔板,问题就转换为9个隔板如何分隔2面蓝旗,共C112)种。此时19个旗子排成一行,为保证每个旗杆至少有一个旗子,旗子之间可以划分旗杆的位置还剩18个,这种情况的总数是18×C112)=990

对于情况2,可以将相邻的2面绿旗看作一个整体,视作一面“虚拟的”绿旗,例如122334等,那么共有8种产生虚拟绿旗方案。此时问题就转换为对10面蓝旗和8面绿旗(其中1面为虚拟绿旗)进行排列,确保绿旗之间互不相邻。8面绿旗必定会锁定7面蓝旗,剩余3面蓝旗,问题等价于8个隔板如何分隔3面蓝旗,共C113)种。从虚拟绿旗中间放置旗杆。此情况数量是8×C113)=1320

综上两种情况,符合题意的排列总数是99013202310

解法4:

考虑两种情况:

情况1,两根旗杆上都挂有蓝旗。这个时候1号旗杆的蓝旗数量是从1~9,相对应地,2号旗杆的蓝旗数量就从9~1。在这9种情况下,任何一种情况都有12位置可供绿旗插入,所以相当于12个位置选9个位置放绿旗,即9×C(12,9)=1980种排列方法。

情况2,其中一根旗杆上没有蓝旗。这个时候,这根旗杆必须要一面绿旗以保证符合题意。那么,剩下的8面绿旗就可以插入11个空位上,即C(11,8);由于两根旗杆可以互换,所以全部的可能性是2×C(11,8)=330种。

因此,综合起来就是:N=9×C(12,9)+2×C(11,8)=1980+330=2310种。

上一篇:

下一篇:

相关阅读

分享