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 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^4 = 256</math> possibilities for each of <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 for an output value.
−
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:
 
  
−
*Case 1: <math>f</math>'s range contains 3 elements
+
We proceed with casework to determine the number of possible <math>f</math> with range 1, 2, etc.
−
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>.
+
*Range 1:
  
−
Note that <math>g</math> can only be the function assigning each element of <math>A</math> to the  element not already chosen.
+
There are 4 possibilities: all elements output to 1, 2, 3, or 4.
  
−
Thus, there are <math>4*3^4</math> ways for that to happen.
+
*Range 2:
  
−
*Case 2: <math>f</math>'s range contains 2 elements
+
We have <math>{{4}\choose {2}} = 6</math> ways to choose the two output elements for <math>f</math>. At this point we have two possibilities: either <math>f</math> has 3 of 1 element and 1 of the other, or 2 of each element. In the first case, there are 2 ways to pick the element which there are 3 copies of, and <math>{{4}\choose {1}} = 4</math> ways to rearrange the 4 elements, for a total of <math>6 * 4 * 2 = 48</math> ways for this case. For the second case, there are <math>{{4}\choose {2}} = 6</math> ways to rearrange the 4 elements, for a total of <math>6 * 6 = 36</math> ways for this case. Adding these two, we get a total of <math>36 + 48 = 84</math> total possibilities.
 +
 
 +
*Range 3:
 +
 
 +
We have <math>{{4}\choose {3}} = 4</math> ways to choose the three output elements for <math>f</math>. We know we must have 2 of 1 element and 1 of each of the others, so there are 3 ways to pick this element. Finally, there are <math>{{4}\choose{1}}*{{3}\choose{1}} = 12</math> ways to rearrange these elements (since we can pick the locations of the 2 single elements in this many ways), and our total is <math>4 * 3 * 12 = 144</math> ways.
  
−
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>.
+
*Range 4:
  
−
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)
+
Since we know the elements present, we have <math>4!</math> ways to arrange them, or 24 ways.
  
−
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.
+
(To check, <math>4 + 84 + 144 + 24 = 256</math>, which is the total number of possibilities).
  
−
So there <math>(6*2^4)(2^4+2)</math> ways for that to happen.
+
We now break <math>f</math> down by cases, and count the number of <math>g</math> whose ranges are disjoint from <math>f</math>'s.
  
−
*Case 3: <math>f</math>'s range contains 1 element
+
*Case 1: <math>f</math>'s range contains 1 element
−
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>.
+
We know that there are 3 possibilities for <math>g</math> with 1 element. Since half the possibilities for <math>g</math> with two elements will contain the element in <math>f</math>, there are <math>84/2 = 42</math> possibilities for <math>g</math> with 2 elements. Since <math>3/4</math> the possibilities for <math>g</math> with 3 elements will contain the element in <math>f</math>, there are <math>144/4 = 36</math> possibilities for <math>f</math> with 3 elements. Clearly, no 4-element range for <math>g</math> is possible, so the total number of ways for this case to happen is <math>4(3 + 42 + 36) = 324</math>.
  
−
Now <math>g</math> can have a range of 1, 2, or 3:
+
*Case 2: <math>f</math>'s range contains 2 elements
−
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.
+
We know that there are 2 possibilities for <math>g</math> with 1 element. If <math>g</math> has 2 elements in its range, they are uniquely determined, so the total number of sets with a range of 2 elements that work for <math>g</math> is <math>84/6 = 14</math>. No 3-element or 4-element ranges for <math>g</math> are possible. Thus, the total number of ways for this to happen is <math>84(2 + 14) = 1344</math>.
  
−
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.
+
*Case 3:  <math>f</math>'s range contains 3 elements
−
Thus, there are <math>4*(3^4+3*2^4+3)</math> ways for that to occur
+
In this case, there is only 1 possibility for <math>g</math> - all the output values are the element that does not appear in <math>f</math>'s range. Thus, the total number of ways for this to happen is <math>144</math>.
  
 
*Summing the cases
 
*Summing the cases
Line 39: Line 40:
 
We find that the probability of <math>f</math> and <math>g</math> having 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*(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>
+
<math>\dfrac{324 + 1344 + 144}{256^2}=\dfrac{1812}{2^{16}}= \dfrac{453}{2^{14}}</math>
  
−
Thus, our final answer is <math>645</math>.
+
Thus, our final answer is <math>453</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2014|n=I|num-b=11|num-a=13}}
 
{{AIME box|year=2014|n=I|num-b=11|num-a=13}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 10:57, 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^4 = 256$ possibilities for each of $f$ and $g$ from $A$ to $A$ since the input of the four values of each function has four options each for an output value.

We proceed with casework to determine the number of possible $f$ with range 1, 2, etc.

  • Range 1:

There are 4 possibilities: all elements output to 1, 2, 3, or 4.

  • Range 2:

We have ${{4}\choose {2}} = 6$ ways to choose the two output elements for $f$. At this point we have two possibilities: either $f$ has 3 of 1 element and 1 of the other, or 2 of each element. In the first case, there are 2 ways to pick the element which there are 3 copies of, and ${{4}\choose {1}} = 4$ ways to rearrange the 4 elements, for a total of $6 * 4 * 2 = 48$ ways for this case. For the second case, there are ${{4}\choose {2}} = 6$ ways to rearrange the 4 elements, for a total of $6 * 6 = 36$ ways for this case. Adding these two, we get a total of $36 + 48 = 84$ total possibilities.

  • Range 3:

We have ${{4}\choose {3}} = 4$ ways to choose the three output elements for $f$. We know we must have 2 of 1 element and 1 of each of the others, so there are 3 ways to pick this element. Finally, there are ${{4}\choose{1}}*{{3}\choose{1}} = 12$ ways to rearrange these elements (since we can pick the locations of the 2 single elements in this many ways), and our total is $4 * 3 * 12 = 144$ ways.

  • Range 4:

Since we know the elements present, we have $4!$ ways to arrange them, or 24 ways.

(To check, $4 + 84 + 144 + 24 = 256$, which is the total number of possibilities).

We now break $f$ down by cases, and count the number of $g$ whose ranges are disjoint from $f$'s.

  • Case 1: $f$'s range contains 1 element

We know that there are 3 possibilities for $g$ with 1 element. Since half the possibilities for $g$ with two elements will contain the element in $f$, there are $84/2 = 42$ possibilities for $g$ with 2 elements. Since $3/4$ the possibilities for $g$ with 3 elements will contain the element in $f$, there are $144/4 = 36$ possibilities for $f$ with 3 elements. Clearly, no 4-element range for $g$ is possible, so the total number of ways for this case to happen is $4(3 + 42 + 36) = 324$.

  • Case 2: $f$'s range contains 2 elements

We know that there are 2 possibilities for $g$ with 1 element. If $g$ has 2 elements in its range, they are uniquely determined, so the total number of sets with a range of 2 elements that work for $g$ is $84/6 = 14$. No 3-element or 4-element ranges for $g$ are possible. Thus, the total number of ways for this to happen is $84(2 + 14) = 1344$.


  • Case 3: $f$'s range contains 3 elements

In this case, there is only 1 possibility for $g$ - all the output values are the element that does not appear in $f$'s range. Thus, the total number of ways for this to happen is $144$.

  • Summing the cases

We find that the probability of $f$ and $g$ having disjoint ranges is equal to:

$\dfrac{324 + 1344 + 144}{256^2}=\dfrac{1812}{2^{16}}= \dfrac{453}{2^{14}}$

Thus, our final answer is $453$.

See also

2014 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 11 		Followed by
Problem 13
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=61030"