Difference between revisions of "2014 AIME I Problems/Problem 12"
(→Problem 12) |
(→Solution) |
||
| 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 ? == |
| + | 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 | ||
| + | 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: fs 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 | ||
| + | |||
| + | note that g can only be the function assigning each element of A to the unchosen element | ||
| + | |||
| + | so there </math>4*<math>3^4</math> for that to happen | ||
| + | |||
| + | *Case 2: fs 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 | ||
| + | |||
| + | 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) | ||
| + | |||
| + | 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 | ||
| + | |||
| + | so there <math>(6*2^4)(2^4+2)</math> ways for that to happen | ||
| + | |||
| + | *case 3: fs 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 | ||
| + | |||
| + | 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 <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 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. | ||
| + | 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: | ||
| + | |||
| + | <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*11}{2^{16}}=\dfrac{3^4+2^4*3^3+11*2^2}{2^{14}}=\dfrac{587}{2^{14}}</math> | ||
| + | so the final answer is <math>587</math> | ||
Revision as of 15:03, 14 March 2014
Problem 12
Let 
, and 
and 
be randomly chosen (not necessarily distinct) functions from 
to . The probability that the range of and the range of are disjoint is 
, where 
and 
are relatively prime positive integers. Find .
Solution ?
we note there are 
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 and has at most four elements
this can be done in 3 cases:
- Case 1: fs range contains 3 elements
there are 4 ways to choose the range of f
then each element in f can be assigned to one of the 3 elements in the range of f so there are 
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 unchosen element
so there$ (Error compiling LaTeX. Unknown error_msg)4*
for that to happen
- Case 2: fs range contains 2 elements
there are 6 ways to choose the range of f
then each element in f can be assigned to one of the 2 elements in the range of f so there are 
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 (
ways)
or g can have a range of one element there are 2 ways to choose its range 
and like in case 1 g can happen in exactly 1 way
so there 
ways for that to happen
- case 3: fs range contains 1 element
here are 4 ways to choose the range of f
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 ways for that to occur.
if g's range contains 2 elements one can choose the 2 elements in 3 different ways 
and after choosing each element has 2 options resulting with ways for that to ocuur
if g's range contains 1 element one can choose the 1 elements in 3 different ways 
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:
so the final answer is 
