Question

有 $25$ 枚不可区分的白色筹码和 $25$ 枚不可区分的黑色筹码。求把其中若干枚筹码放入一个 $5 \times 5$ 方格中的方法数，使得：

• 每个格子至多含一枚筹码

• 同一行中的所有筹码颜色相同，且同一列中的所有筹码颜色相同，并且

• 再向方格中放入任何一枚筹码，都会违反前两个条件中的一个或多个。

There is a collection of $25$ indistinguishable white chips and $25$ indistinguishable black chips. Find the number of ways to place some of these chips in a $5 \times 5$ grid such that:

• each cell contains at most one chip

• all chips in the same row and all chips in the same column have the same color, and

• any additional chip placed on the grid would violate one or more of the previous two conditions.

答案

答案：902

知识点：有限制的排列极端原理乘法原理

难度评级：2920

解答：

在一个合法摆放中，每个非空行只有一种颜色，每个非空列也同理。如果某一行为空，任选其中一个格子：可以放入一枚与该格所在列颜色相同的筹码（若该列也为空，则任选颜色），这与第三个条件矛盾。所以每一行和每一列都非空，我们可以谈论它们的颜色。

某格有筹码会迫使其行颜色与列颜色相同；反过来，若一行和一列颜色相同但它们交叉的格子为空，就可以加入一枚该颜色的筹码。因此筹码恰好占据行颜色等于列颜色的格子。为了让每一行非空，每个行颜色必须出现在列颜色中，反之亦然，即行与列使用同一组颜色。任何这样的染色反过来都会给出一个合法的极大摆放（每种颜色至多占 $25$ 个格子，筹码数量足够），且不同染色给出不同摆放。

计数这些染色：所有行列全白、所有行列全黑，或者行和列都使用两种颜色： $1 + 1 + (2^5 - 2)^2 = 2 + 900$ $= 902$ 。

In a valid placement, each nonempty row has a single color, and likewise each column. If some row were empty, choose any cell of it: a chip of the color of that cell's column (either color if the column is also empty) could legally be added, contradicting the third condition. So every row and every column is nonempty, and we may speak of its color.

A chip at a cell forces its row and column colors to agree; conversely, if a row and a column share a color but their common cell is empty, a chip of that color could be added. Hence chips occupy exactly the cells whose row color equals the column color. For every row to be nonempty, each row's color must appear among the column colors, and vice versa — the rows and the columns use the same set of colors. Any such coloring conversely yields a valid maximal placement (at most $25$ cells hold chips of each color, so the supply suffices), and distinct colorings give distinct placements.

Counting the colorings: all rows and columns white, all black, or both colors used by the rows and by the columns: $1 + 1 + (2^5 - 2)^2 = 2 + 900$ $= 902.$

2024 AIME II 第 9 题

答案：902

难度评级：2920

解答：

其他年份的第 9 题