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 ??)
(→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
We note there are <math>4^8</math> sets of two functions <math>f</math> and <math>g</math> from <math>A</math> to <math>A</math> since the input of the four values of each function has four options each
+
We note there are <math>4^8</math> sets of two functions <math>f</math> and <math>g</math> from <math>A</math> to <math>A</math> since the input of the four values of each function has four options each.
−
By the pigeonhole principle the combined range  of <math>f</math> and <math>g</math> has at most four elements
+
By the pigeonhole principle, the combined range  of <math>f</math> and <math>g</math> has at most four elements
 
this can be done in 3 cases:
 
this can be done in 3 cases:
  
 
*Case 1: <math>f</math>'s range contains 3 elements
 
*Case 1: <math>f</math>'s range contains 3 elements
−
there are 4 ways to choose the range of <math>f</math> <math>{{4}\choose {3}}</math> then three elements of A can be assigned in <math>0.5*3*4*(3!)</math> ways: choose which element will be assigned to more than once (3) how three elements will be assigned to to three elements of A(6)  which of the four elements will be assigned to the extra value, divided by 2 becuase of over-counting
+
There are 4 ways to choose the range of <math>f</math> <math>{{4}\choose {3}}</math> then each element in <math>f</math> can be assigned to one of the 3 elements in the range of <math>f</math> so there are <math>4*3^4</math> functions with a range of 3 elements in <math>A</math>.
−
 
−
note that <math>g</math> can only be the function assigning each element of <math>A</math> to the  element not already chosen
 
  
−
so there <math>4*36</math> for that to happen
+
Note that <math>g</math> can only be the function assigning each element of <math>A</math> to the  element not already chosen.
 +
 
 +
Thus, there are <math>4*3^4</math> ways for that to happen.
  
 
*Case 2: <math>f</math>'s range contains 2 elements
 
*Case 2: <math>f</math>'s range contains 2 elements
  
−
there are 6 ways to choose the range of <math>f</math> <math>{{4}\choose {2}}</math> then each element in <math>f</math> can be assigned to one of the 2 elements in the range of <math>f</math> so there are <math>4*2^4</math> functions with a range of 3 elements in <math>A</math>
+
there are 6 ways to choose the range of <math>f</math> <math>{{4}\choose {2}}</math> then each element in <math>f</math> can be assigned to one of the 2 elements in the range of <math>f</math> so there are <math>4*2^4</math> functions with a range of 3 elements in <math>A</math>.
  
−
now <math>g</math> can have a range of two elements in which each of its 4 values can be assigned one of its elements (<math>2^4-2</math> ways)
+
Now <math>g</math> can have a range of two elements in which each of its 4 values can be assigned one of its elements (<math>2^4</math> ways)
  
−
or <math>g</math> can have a range of one element there are 2 ways to choose its range <math>{{2}\choose {1}}</math> and like in case 1 <math>g</math> can happen in exactly 1 way
+
Also, <math>g</math> can have a range of one element there are 2 ways to choose its range <math>{{2}\choose {1}}</math>, and like in case 1, <math>g</math> can happen in exactly 1 way.
  
−
so there <math>(6*(2^4-2))(2^4)</math> ways for that to happen
+
So there <math>(6*2^4)(2^4+2)</math> ways for that to happen.
  
−
*case 3:  <math>f</math>'s range contains 1 element
+
*Case 3:  <math>f</math>'s range contains 1 element
−
here are 4 ways to choose the range of <math>f</math> <math>{{4}\choose {1}}</math> then each element in <math>A</math> can be assigned to only one value so there are 4 functions with a range of 1 elements in <math>A</math>
+
There are 4 ways to choose the range of <math>f</math>, given by <math>{{4}\choose {1}}</math>. We then know that each element in <math>A</math> can be assigned to only one value, so there are 4 functions with a range of 1 element in <math>A</math>.
  
−
now <math>g</math> can have a range of 1,2 or 3:
+
Now <math>g</math> can have a range of 1, 2, or 3:
−
if <math>g</math>'s range has 3 elements each value in <math>A</math> can be assigned to 3 other values so there <math>3^4</math> ways for that to occur.
+
If <math>g</math>'s range has 3 elements each value in <math>A</math> can be assigned to 3 other values so there <math>3^4</math> ways for that to occur.
  
−
if <math>g</math>'s range contains 2 elements one can choose the 2 elements in 3 different ways  <math>{{3}\choose {2}}</math> and after choosing each element has 2 options resulting with <math>2^4</math> ways for that to occur
+
If <math>g</math>'s range contains 2 elements one can choose the 2 elements in 3 different ways  <math>{{3}\choose {2}}</math> and after choosing each element has 2 options resulting with <math>2^4</math> ways for that to occur
  
−
if <math>g</math>'s range contains 1 element one can choose the 1 elements in 3 different ways  <math>{{3}\choose {1}}</math> and after choosing each element has 1 option resulting with 1 way for that to happen.
+
If <math>g</math>'s range contains 1 element one can choose the 1 elements in 3 different ways  <math>{{3}\choose {1}}</math> and after choosing each element has 1 option resulting with 1 way for that to happen.
−
so there are <math>4*(3^4)</math> ways for that to occur
+
Thus, there are <math>4*(3^4+3*2^4+3)</math> ways for that to occur
  
−
*summing the cases
+
*Summing the cases
  
−
we get that the probability for <math>f</math> and <math>g</math> to have disjoint ranges is equal to:
+
We find that the probability of <math>f</math> and <math>g</math> having disjoint ranges is equal to:
  
−
<math>\dfrac{4*3^4+(6*2^4)(2^4-2)+4*(36)}{4^8} =\dfrac{2^2*3^4+2^6*3*7+2^4*3^2}{2^{16}}= \dfrac{3^4+2^4*3*7+3^2*2^2}{2^{14}}=\dfrac{453}{2^{14}}</math>
+
<math>\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}}</math>
−
so the final answer is <math>453</math>
 
  
−
== See also ==
+
Thus, our final answer is <math>645</math>.
−
{{AIME box|year=2014|n=I|num-b=11|num-a=13}}
 
−
{{MAA Notice}}
 

Revision as of 21:07, 14 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$.

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