棋盘上的组合数学问题

橘子网 2,952 0

题目:比阿特丽克斯(Beatrix)将在6×6的棋盘上放置6个“车”,其中行和列从1标记到6。规定:“车”的位置满足任意两个车不能放在同一行或同一列。正方形的值(value)定义为其行标号与列标号之和。“车”放法的分数(score)定义为所有被占用的正方形的值的最小值。所有满足条件方法的平均数是p/q,其中p和q是互质的正整数。求p+q的值。(2016 AIME II)

棋盘上的组合数学问题

这道题是2016年美国数学邀请赛卷二的第13题(一共15题),是属于难度较大的题目了。在这道题中,理解题目的意思是关键,否则可能很难下手。这里允许读者朋友们先思考二十分钟,然后再看后面的解答。

题意分析:首先我们要理解两个关键的句子,也就是其中的两个“定义”。

(1)正方形的值(value)定义为其行标号与列标号之和。这句话相对容易理解。就是横坐标和纵坐标的数值之和。

棋盘上的组合数学问题

(2)“车”放法的分数(score)定义为所有被占用的正方形的值的最小值。这句话是这里的关键,它的意思如下图所示:

棋盘上的组合数学问题 棋盘上的组合数学问题

上图标红色的数字就是所谓的“所有被占用的正方形的值的最小值”。我们可以发现,这个分数最小是2,最大是7

显然,6个“车”放到不同行、不同列的6×6棋盘上,全部可能的放法一共有6!=720种。我们要做的,就是把这720种放法的最小分数(score)加总后求平均数。

解法一:按最低分数分类讨论(1)当最低分数为2时,这个最低分数的“车”只能放在(1,1)坐标的格子中,则其他5个“车”有5!种方法(或者6!-5×5×4!=120种),所以这种情况的总分为2×120=240分;棋盘上的组合数学问题

棋盘上的组合数学问题(2)当最低分数为3时,由于(1,1)坐标的格子中不能放“车”,因此这个最低分数的“车”只能放在(1,2)或(2,1)坐标的格子中,很容易计算共有5!×2-4!=216种(或者4×4!×2+4!=9×4!=216种;或者6!-4×4×4!-120=216种)放法,所以这种情况的总分为3×216=648分;

棋盘上的组合数学问题

(3)当最低分数为4时,由于(1,1)、(1,2)、(2,1)坐标的格子中均不能放“车”,因此这个最低分数的“车”只能放在(1,3)、(3,1)或(2,2)坐标的格子中,很容易计算共有3×3×3!×3+3×3!×3+3!=222种放法(或者6!-3×3×3×3!-216-120=222种),所以这种情况的总分为4×222=888分;

棋盘上的组合数学问题

(4)当最低分数为5时,由于(1,1)、(1,2)、(2,1)、(1,3)、(3,1)坐标的格子中均不能放“车”,因此这个最低分数的“车”只能放在(1,4)、(2,3)、(3,2)、(4,1)坐标的格子中,很容易计算共有6!-2×2×2×2×2!-222-216-120=130种放法,所以这种情况的总分为5×130=650分;

棋盘上的组合数学问题

(5)当最低分数为6时,由于(1,1)、(1,2)、(2,1)、(1,3)、(3,1)、(1,4)、(2,3)、(3,2)、(4,1)坐标的格子中均不能放“车”,因此这个最低分数的“车”只能放在(1,5)、(2,4)、(3,3)、(4,2)、(5,1)坐标的格子中,很容易计算共有6!-1-130-222-216-120=31种放法,所以这种情况的总分为6×31=186分;

棋盘上的组合数学问题(6)当最低分数为7时,由于(1,1)、(1,2)、(2,1)、(1,3)、(3,1)、(1,4)、(2,3)、(3,2)、(4,1)、(1,5)、(2,4)、(3,3)、(4,2)、(5,1)坐标的格子中均不能放“车”,因此这个最低分数的“车”只能放在(1,6)、(2,5)、(3,4)、(4,3)、(5,2)、(6,1)坐标的格子中,显然只有唯一的1种放法,所以这种情况的总分为7×1=7分。

棋盘上的组合数学问题

综上,总分为240+648+888+650+186+7=2619分,所以平均数为2619/720=291/80,故p+q=291+80=371。

解法二:思路同上,计算简化。假设An为最低分数恰好是n放法的种数,Bn为最低分数至少是n放法的种数。于是可得:

2A2+3A3+4A4+5A5+6A6+7A7=2(A2+A3+…+A7)+(A3+…+A7)+(A4+…+A7)+…+(A6+A7)+A7=2B2+B3+B4+B5+B6+B7

由于每种放法至少有2分,则B2=6!=720种;B3等于在(1,1)位置上不放“车”的放法,故B3=5×5!=600种;B4的计算,第一行有4个位置可选,第二行也有4个位置可选,剩下的4个“车”有4!中放法,则B4=4×4×4!=384种;同理,B5=3×3×3×3!=162种,B6=2×2×2×2×2!=32种,B7=1×1×1×1×1×1!=1种。

因此总分为2×720+600+384+162+32+1=2619种。

平均数计算同解法一,略。

解法三:我们经过摆放“车”可以发现,凡是分数为n+1的“车”,一定是出现在这个棋盘的一条反向对角线上。以n=4为例,如下图所示:

棋盘上的组合数学问题

这里的思路是,把这条反向对角线及以上“车”的放法,减去反向对角线上方“车”的放法,就是最低分数为n+1的“车”的全部方法。

以n=4为例。

(1)计算反向对角线及以上“车”的放法。因为,对于第一行来说,“车”有3个位置可以放,第二行也有3个位置可以放,第三行同样有3个位置可以放,第四行还有3个位置可以放,剩下的两个“车”有2!种放法,所以对于前4个“车”来说,有34种放法,共有34×2!种放法。

(2)计算反向对角线上方“车”的放法。同理可得,对于前4个“车”来说,有24种放法,共有24×2!种放法。

综上,对于最低分数为5“车”的放法而言,共有(34-24) ×2!种。我们可以一般化地推出,对于最低分数为n+1的“车”来说,共有((7-n)n-(6-n)n)×(6-n)!种放法。

于是可得总分为:2×(61-51)×5!+3×(52-42)×4!+4×(43-33)×3!+5×(34-24)×2!+6×(25-15)×1!+7×(16-06)×0!=240+648+888+650+186+7=2619种。

平均数计算同解法一,略。

上一篇:

下一篇:

相关阅读

分享