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 ??)
m (WHY DOES THIS SOLUTION WORK)
 
(17 intermediate revisions by 8 users not shown)
Line 2: Line 2:
 
Let <math>A=\{1,2,3,4\}</math>, and <math>f</math> and <math>g</math> be randomly chosen (not necessarily distinct) functions from <math>A</math> to <math>A</math>. The probability that the range of <math>f</math> and the range of <math>g</math> are disjoint is <math>\tfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m</math>.
 
Let <math>A=\{1,2,3,4\}</math>, and <math>f</math> and <math>g</math> be randomly chosen (not necessarily distinct) functions from <math>A</math> to <math>A</math>. The probability that the range of <math>f</math> and the range of <math>g</math> are disjoint is <math>\tfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m</math>.
  
−
== Solution ==
+
==Solution 1 (casework)==
−
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
+
The natural way to go is casework. And the natural process is to sort <math>f</math> and <math>g</math> based on range size! Via Pigeonhole Principle, we see that the only real possibilities are: <math>f 1 g 1; f 1 g 2; f 1 g 3; f 2 g 2</math>. Note that the <math>1, 2</math> and <math>1, 3</math> cases are symmetrical and we need just a <math>*2</math>. Note also that the total number of cases is <math>4^4*4^4=4^8</math>.
−
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
+
<math>f 1 g 1</math>: clearly, we choose one number as the range for <math>f</math>, one for <math>g</math>, yielding <math>12</math> possibilities.
−
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
 
−
 
−
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
+
<math>f 1 g 2</math> with symmetry (WLOG <math>f</math> has 1 element): start by selecting numbers for the ranges. This yields <math>4</math> for the one number in <math>f</math>, and <math>3</math> options for the two numbers for <math>g</math>. Afterwards, note that the function with 2 numbers in the range can have <math>4+6+4=14</math> arrangements of these two numbers (1 of one, 3 of the other *2 and 2 of each). Therefore, we have <math>2*12*14</math> possibilities, the 2 from symmetry.
 +
 
 +
<math>f 2 g 2</math>: no symmetry, still easy! Just note that we have <math>6</math> choices of which numbers go to <math>f</math> and <math>g</math>, and within each, <math>14*14=196</math> choices for the orientation of each of the two numbers. That's <math>6*196</math> possibilities.
 +
 
 +
<math>f 1 g 3</math>: again, symmetrical (WLOG <math>f</math> has one element): <math>4</math> ways to select the single element for <math>f</math>, and then find the number of ways to distribute the <math>3</math> distinct numbers in the range for <math>g</math>. The only arrangement for the frequency of each number is <math>{1, 1, 2}</math> in some order. Therefore, we have <math>3</math> ways to choose which number is the one represented twice, and then note that there are <math>12</math> ways to arrange these! The number of possibilities in this situation is <math>2 * 4 * 3 * 12</math>.
 +
 
 +
Total, divided by <math>4^8</math>, gets <math>\frac{3 * (1 + 2 * 7^2 + 2^2 * 7 + 2^3 * 3)}{4^7}</math>, with numerator <math>\boxed{453}</math>.
 +
 
 +
==Solution 2 (casework)==
 +
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.
 +
 
 +
We proceed with casework to determine the number of possible <math>f</math> with range 1, 2, etc.
 +
*Range 1:
 +
 
 +
There are 4 possibilities: all elements output to 1, 2, 3, or 4.
 +
 
 +
*Range 2:
 +
 
 +
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.
 +
 
 +
*Range 4:
 +
 
 +
Since we know the elements present, we have <math>4!</math> ways to arrange them, or 24 ways.
 +
 
 +
(To check, <math>4 + 84 + 144 + 24 = 256</math>, which is the total number of possibilities).
 +
 
 +
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 1: <math>f</math>'s range contains 1 element
 +
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>g</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>.
  
 
*Case 2: <math>f</math>'s range contains 2 elements
 
*Case 2: <math>f</math>'s range contains 2 elements
 +
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>.
  
−
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)
+
*Case 3:  <math>f</math>'s range contains 3 elements
 +
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>.
  
−
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
+
*Summing the cases
  
−
so there <math>(6*(2^4-2))(2^4)</math> ways for that to happen
+
We find that the probability of <math>f</math> and <math>g</math> having disjoint ranges is equal to:
  
−
*case 3:  <math>f</math>'s range contains 1 element
+
<math>\dfrac{324 + 1344 + 144}{256^2}=\dfrac{1812}{2^{16}}= \dfrac{453}{2^{14}}</math>
−
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>
 
  
−
now <math>g</math> can have a range of 1,2 or 3:
+
Thus, our final answer is <math>\boxed{453}</math>.
−
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
+
=== Solution 3 (simplification of Solution 2) ===
 +
As before, there are 4 functions with a range of size 1, 84 with a range of size 2, and 144 with a range of size 3. If the range of <math>f</math> has size <math>k</math>, the codomain of <math>g</math> is restricted to a set of size <math>4 - k</math>. Any function from <math>A</math> into this codomain will do, so there are <math>(4 - k)^4</math> possibilities for <math>g</math> given a function <math>f</math>. The probability of <math>f</math> and <math>g</math> having disjoint ranges is then
 +
<cmath>\frac{4\cdot 3^4 + 84\cdot 2^4 + 144\cdot 1^4}{(4^4)^2} = \frac{\boxed{453}}{2^{14}}.</cmath>
  
−
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
 
  
−
*summing the cases
+
==Video Solution==
 +
https://youtu.be/VFj6JesV93M?si=cDAOday30X0O__4T
  
−
we get that the probability for <math>f</math> and <math>g</math> to have disjoint ranges is equal to:
+
~MathProblemSolvingSkills.com
  
−
<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>
 
−
so the 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}}

Latest revision as of 21:31, 13 October 2023

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 1 (casework)

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 $\boxed{453}$.

Solution 2 (casework)

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 $g$ 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 $\boxed{453}$.

Solution 3 (simplification of Solution 2)

As before, there are 4 functions with a range of size 1, 84 with a range of size 2, and 144 with a range of size 3. If the range of $f$ has size $k$, the codomain of $g$ is restricted to a set of size $4 - k$. Any function from $A$ into this codomain will do, so there are $(4 - k)^4$ possibilities for $g$ given a function $f$. The probability of $f$ and $g$ having disjoint ranges is then \[\frac{4\cdot 3^4 + 84\cdot 2^4 + 144\cdot 1^4}{(4^4)^2} = \frac{\boxed{453}}{2^{14}}.\]


Video Solution

https://youtu.be/VFj6JesV93M?si=cDAOday30X0O__4T

~MathProblemSolvingSkills.com


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=199615"