Question

设 $A = \{1, 2, 3, 4\}$ ，并从 $A$ 到 $A$ 的所有函数中随机选择函数 $f$ 和 $g$ （二者不一定不同）。 $f$ 的值域与 $g$ 的值域不相交的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m$ 。

Let $A = \{1, 2, 3, 4\},$ and let $f$ and $g$ be randomly chosen (not necessarily distinct) functions from $A$ to $A.$ The probability that the range of $f$ and the range of $g$ are disjoint is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m.$

答案

答案：453

知识点：函数基本概率分类讨论

难度评级：2990

解答：

按 $f$ 的值域分类。若它有 $k$ 个元素，则 $g$ 的值域与其不相交，当且仅当 $g$ 把 $A$ 映到剩下的 $4 - k$ 个元素中；在全部 $4^4 = 256$ 个函数中，这样的 $g$ 有 $(4-k)^4$ 个。

按值域大小计数 $f$ ：常值函数有 $4$ 个；值域大小为 $2$ 的有 $\binom{4}{2}(2^4 - 2) = 84$ 个；值域大小为 $3$ 的有 $\binom{4}{3} \cdot 36 = 144$ 个（从四个元素满射到三个元素有 $36$ 个）；双射有 $4! = 24$ 个。有利的有序函数对数量为 $\begin{aligned} &4 \cdot 3^4 + 84 \cdot 2^4 \\ &\quad {}+ 144 \cdot 1^4 + 24 \cdot 0^4 \\ &= 324 + 1344 + 144 = 1812. \end{aligned}$

概率为 $\frac{1812}{4^8} = \frac{1812}{65536} = \frac{453}{16384}$ ，由于 $16384$ 是 $2$ 的幂，而 $453 = 3 \cdot 151$ 为奇数，此分数已是最简。因此 $m = 453$ 。

Condition on the range of $f.$ If it has $k$ elements, then the range of $g$ is disjoint from it exactly when $g$ maps $A$ into the remaining $4 - k$ elements, which happens for $(4-k)^4$ of the $4^4 = 256$ functions $g.$

Count functions $f$ by range size: $4$ constant functions; $\binom{4}{2}(2^4 - 2) = 84$ with range size $2;$ $\binom{4}{3} \cdot 36 = 144$ with range size $3$ (there are $36$ surjections from four elements onto three); and $4! = 24$ bijections. The number of favorable pairs is $\begin{aligned} &4 \cdot 3^4 + 84 \cdot 2^4 \\ &\quad {}+ 144 \cdot 1^4 + 24 \cdot 0^4 \\ &= 324 + 1344 + 144 = 1812. \end{aligned}$

The probability is $\frac{1812}{4^8} = \frac{1812}{65536} = \frac{453}{16384},$ and since $16384$ is a power of $2$ while $453 = 3 \cdot 151$ is odd, this is in lowest terms. Thus $m = 453.$

2014 AIME I 第 12 题

答案：453

难度评级：2990

解答：

其他年份的第 12 题