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  f and g from A to A 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: fs range contains 3 elements
+
*Case 1: <math>f</math>'s range contains 3 elements
−
there are 4 ways to choose the range of f<math>{{4}\choose {3}}</math> then each element in f can be assigned to one of the 3 elements in the range of f so there are <math>4*</math>3^4<math> functions with a range of 3 elements in A
+
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 g can only be the function assigning each element of A to the unchosen element
+
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*<math>3^4</math> for that to happen
+
so there <math>4*3^4</math> for that to happen
  
−
*Case 2: fs range contains 2 elements
+
*Case 2: <math>f</math>'s range contains 2 elements
  
−
there are 6 ways to choose the range of f<math>{{4}\choose {2}}</math> then each element in f can be assigned to one of the 2 elements in the range of f so there are <math>4*2^4</math> functions with a range of 3 elements in A
+
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 g 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)
+
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 g 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 g can happen in exactly 1 way
+
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
  
 
so there <math>(6*2^4)(2^4+2)</math> ways for that to happen
 
so there <math>(6*2^4)(2^4+2)</math> ways for that to happen
  
−
*case 3:  fs range contains 1 element
+
*case 3:  <math>f</math>'s range contains 1 element
−
here are 4 ways to choose the range of f<math>{{4}\choose {1}}</math> 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
+
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 g can have a range of 1,2 or 3:
+
now <math>g</math> 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 <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 g'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 ocuur
+
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 g'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 4*(3^4+3*2^4+3) ways for that to occur
+
so there are <math>4*(3^4+3*2^4+3)</math> ways for that to occur
  
−
summing the cases we get that the probability for f and g to have disjoint ranges is equal to:
+
summing the cases we get that the probability for <math>f</math> and <math>g</math> to have 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{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>645</math>
 
so the final answer is <math>645</math>

Revision as of 16:51, 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

so there $4*3^4$ 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)

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: $f$'s 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 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. 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$

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