Question

设 $A = \{1, 2, 3, 4\}$ ，并随机选择两个函数 $f$ 和 $g$ （二者不一定不同），它们都从 $A$ 映射到 $A$ 。 $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$ 个元素，则恰有 $(4-k)^4$ 个函数 $g$ 的值域与它不相交

If the range of $f$ has $k$ elements, exactly $(4-k)^4$ functions $g$ have range disjoint from it

大提示：

按值域大小计数函数：数量依次为 $4$ 个（值域大小 $1$ ）、 $84$ 个（值域大小 $2$ ）、 $144$ 个（值域大小 $3$ ）、 $24$ 个（值域大小 $4$ ）

Count functions by range size: $4$ with size $1,$ $84$ with size $2,$ $144$ with size $3,$ $24$ with size $4$

解答：

按 $f$ 的值域分类。若它有 $k$ 个元素，则 $g$ 的值域与其不相交，当且仅当 $g$ 把 $A$ 映到剩下的 $4 - k$ 个元素中；满足条件的映射方式有 $(4-k)^4$ 种，全部共有 $4^4 = 256$ 个函数 $g$ 。

按值域大小计数 $f$ ：常值函数有 $4$ 个；另有 $\binom{4}{2}(2^4 - 2) = 84$ 个函数的值域大小为 $2$ ；另有 $\binom{4}{3} \cdot 36 = 144$ 个函数的值域大小为 $3$ （从四个元素满射到三个元素有 $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}\text{。}$

概率为 $\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 题