棋盘上的组合数学问题

题目：比阿特丽克斯(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。

解法二：思路同上，计算简化。假设A_n为最低分数恰好是n放法的种数，B_n为最低分数至少是n放法的种数。于是可得：

2A₂＋3A₃＋4A₄＋5A₅＋6A₆＋7A₇＝2(A₂＋A₃＋…＋A₇)＋(A₃＋…＋A₇)＋(A₄＋…＋A₇)＋…＋(A₆＋A₇)＋A₇＝2B₂＋B₃＋B₄＋B₅＋B₆＋B₇

由于每种放法至少有2分，则B₂＝6!＝720种；B₃等于在(1,1)位置上不放“车”的放法，故B₃＝5×5!＝600种；B₄的计算，第一行有4个位置可选，第二行也有4个位置可选，剩下的4个“车”有4!中放法，则B₄＝4×4×4!＝384种；同理，B₅＝3×3×3×3!＝162种，B₆＝2×2×2×2×2!＝32种，B₇＝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个“车”来说，有3⁴种放法，共有3⁴×2!种放法。

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

综上，对于最低分数为5“车”的放法而言，共有(3⁴－2⁴) ×2!种。我们可以一般化地推出，对于最低分数为n＋1的“车”来说，共有((7－n)ⁿ－(6－n)ⁿ)×(6－n)!种放法。

于是可得总分为：2×(6¹－5¹)×5!＋3×(5²－4²)×4!＋4×(4³－3³)×3!＋5×(3⁴－2⁴)×2!＋6×(2⁵－1⁵)×1!＋7×(1⁶－0⁶)×0!＝240＋648＋888＋650＋186＋7＝2619种。

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