AIME 2014 I, Problem 12

Let $A=\{1,2,3,4\}$, and $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 $\tfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m$.

Solution: The natural way to go is casework. And the natural process is to sort $f$ and $g$ based on range size! Via Pigeonhole Principle, we see that the only real possibilities are: $f 1 g 1; f 1 g 2; f 1 g 3; f 2 g 2$. Note that the $1, 2$ and $1, 3$ cases are symmetrical and we need just a $*2$. Note also that the total number of cases is $4^4*4^4=4^8$. $f 1 g 1$: clearly, we choose one number as the range for $f$, one for $g$, yielding $12$ possibilities. $f 1 g 2$ with symmetry (WLOG $f$ has 1 element): start by selecting numbers for the ranges. This yields $4$ for the one number in $f$, and $3$ options for the two numbers for $g$. Afterwards, note that the function with 2 numbers in the range can have $4+6+4=14$ arrangements of these two numbers (1 of one, 3 of the other *2 and 2 of each). Therefore, we have $2*12*14$ possibilities, the 2 from symmetry. $f 2 g 2$: no symmetry, still easy! Just note that we have $6$ choices of which numbers go to $f$ and $g$, and within each, $14*14=196$ choices for the orientation of each of the two numbers. That's $6*196$ possibilities. $f 1 g 3$: again, symmetrical (WLOG $f$ has one element): $4$ ways to select the single element for $f$, and then find the number of ways to distribute the $3$ distinct numbers in the range for $g$. The only arrangement for the frequency of each number is ${1, 1, 2}$ in some order. Therefore, we have $3$ ways to choose which number is the one represented twice, and then note that there are $12$ ways to arrange these! The number of possibilities in this situation is $2 * 4 * 3 * 12$. Total, divided by $4^8$, gets $\frac{3 * (1 + 2 * 7^2 + 2^2 * 7 + 2^3 * 3)}{4^7}$, with numerator $\fbox{453}$.

Answer: 453