Question

Robert 有 $4$ 枚无法区分的金币和 $4$ 枚无法区分的银币。每枚硬币的一面刻有人脸，另一面没有。他想把这八枚硬币在桌上叠成一摞，使得没有两枚相邻硬币是人脸对着人脸。求 $8$ 枚硬币可能的可区分排列数。

Robert has $4$ indistinguishable gold coins and $4$ indistinguishable silver coins. Each coin has an engraving of a face on one side, but not on the other. He wants to stack the eight coins on a table into a single stack so that no two adjacent coins are face to face. Find the number of possible distinguishable arrangements of the $8$ coins.

答案

答案：630

知识点：有限制的排列组合乘法原理

难度评级：2300

解答：

独立地选择硬币朝向以及金银位置。把从底到顶的朝向记录成由 U（刻有人脸的一面朝上）和 D（刻有人脸的一面朝下）组成的字符串。两枚相邻硬币人脸对着人脸，当且仅当下方硬币的刻面朝上而上方硬币的刻面朝下，也就是当且仅当一个 U 后面紧接着一个 D。

一个由 U 和 D 组成的字符串避免模式 UD，当且仅当每个 D 都在每个 U 之前，所以字符串形如 $\text{D}^i\text{U}^{8-i}$ ，其中 $i = 0, 1, \ldots, 8$ ：共有 $9$ 种允许的朝向字符串。独立地，金币占据 $8$ 个位置中的 $4$ 个，有 $\binom{8}{4} = 70$ 种方式。

总数为 $9 \cdot 70 = 630$ 。

Choose the coin orientations and the gold/silver positions independently. Record the orientations from bottom to top as a string of U (engraved face up) and D (engraved face down). Two adjacent coins are face to face exactly when the lower coin's engraved side faces up and the upper coin's engraved side faces down — that is, exactly when a U is immediately followed by a D.

A string of U's and D's avoids the pattern UD exactly when every D precedes every U, so the string is $\text{D}^i\text{U}^{8-i}$ for some $i = 0, 1, \ldots, 8:$ there are $9$ allowable orientation strings. Independently, the gold coins occupy $4$ of the $8$ positions in $\binom{8}{4} = 70$ ways.

The total is $9 \cdot 70 = 630.$

2005 AIME I 第 5 题

答案：630

难度评级：2300

解答：

其他年份的第 5 题