Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 AIME I Problems/Problem 12"

(→‎Solution)
Line 42: Line 42:
  
 
Thus, our final answer is <math>645</math>.
 
Thus, our final answer is <math>645</math>.
 +
 +
== See also ==
 +
{{AIME box|year=2014|n=I|num-b=10|num-a=12}}
 +
{{MAA Notice}}

Revision as of 10:02, 15 March 2014

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: $f$'s 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 element not already chosen.

Thus, there are $4*3^4$ ways for that to happen.

  • Case 2: $f$'s 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)

Also, $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: $f$'s range contains 1 element

There are 4 ways to choose the range of $f$, given by ${{4}\choose {1}}$. We then know that each element in $A$ can be assigned to only one value, so there are 4 functions with a range of 1 element 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 occur

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. Thus, there are $4*(3^4+3*2^4+3)$ ways for that to occur

  • Summing the cases

We find that the probability of $f$ and $g$ having 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}}$

Thus, our final answer is $645$.

See also

2014 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_I_Problems/Problem_12&oldid=61028"