2014 AIME I Problems/Problem 12

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 ?

we note there are $4^8$ sets of two functions f and g from A to A since the input of the four values of each function has four options each By the pigeonhole principle the combined range of $f$ and $g$ has at most four elements this can be done in 3 cases:

Case 1: fs range contains 3 elements

there are 4 ways to choose the range of f ${{4}\choose {3}}$ then each element in f can be assigned to one of the 3 elements in the range of f so there are $4*$ 3^4$functions with a range of 3 elements in A

note that g can only be the function assigning each element of A to the unchosen element

so there$ (Error compiling LaTeX. Unknown error_msg)4* $3^4$ for that to happen

Case 2: fs range contains 2 elements

there are 6 ways to choose the range of f ${{4}\choose {2}}$ then each element in f can be assigned to one of the 2 elements in the range of f so there are $4*2^4$ functions with a range of 3 elements in A

now g can have a range of two elements in which each of its 4 values can be assigned one of its elements ( $2^4$ ways)

or g can have a range of one element there are 2 ways to choose its range ${{2}\choose {1}}$ and like in case 1 g can happen in exactly 1 way

so there $(6*2^4)(2^4+2)$ ways for that to happen

case 3: fs range contains 1 element

here are 4 ways to choose the range of f ${{4}\choose {1}}$ then each element in A can be assigned to only one value so there are 4 functions with a range of 1 elements in A

now g can have a range of 1,2 or 3: if g's range has 3 elements each value in A can be assigned to 3 other values so there $3^4$ ways for that to occur.

if g's range contains 2 elements one can choose the 2 elements in 3 different ways ${{3}\choose {2}}$ and after choosing each element has 2 options resulting with $2^4$ ways for that to ocuur

if g's range contains 1 element one can choose the 1 elements in 3 different ways ${{3}\choose {1}}$ and after choosing each element has 1 option resulting with 1 way for that to happen. so there are 4*(3^4+3*2^4+3) ways for that to occur

summing the cases we get that the probability for f and g to have disjoint ranges is equal to:

$\dfrac{4*3^4+(6*2^4)(2^4+2)+4*(3^4+3*2^4+3)}{4^8}=\dfrac{2^2*3^4+2^6*3^3+2^4*3*11}{2^{16}}=\dfrac{3^4+2^4*3^3+3*11*2^2}{2^{14}}=\dfrac{645}{2^{14}}$ so the final answer is $645$

Page

Toolbox

Search

2014 AIME I Problems/Problem 12

Problem 12

Solution ?