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: | + | *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* | + | 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 | + | 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 < | + | so there <math>4*3^4</math> for that to happen |
− | *Case 2: | + | *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: | + | *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 | + | 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 17:51, 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
and
from
to
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:
's range contains 3 elements
there are 4 ways to choose the range of
then each element in
can be assigned to one of the 3 elements in the range of
so there are
functions with a range of 3 elements in
note that can only be the function assigning each element of
to the element not already chosen
so there for that to happen
- Case 2:
's range contains 2 elements
there are 6 ways to choose the range of
then each element in
can be assigned to one of the 2 elements in the range of
so there are
functions with a range of 3 elements in
now can have a range of two elements in which each of its 4 values can be assigned one of its elements (
ways)
or can have a range of one element there are 2 ways to choose its range
and like in case 1
can happen in exactly 1 way
so there ways for that to happen
- case 3:
's range contains 1 element
here are 4 ways to choose the range of
then each element in
can be assigned to only one value so there are 4 functions with a range of 1 elements in
now can have a range of 1,2 or 3:
if
's range has 3 elements each value in
can be assigned to 3 other values so there
ways for that to occur.
if '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 occur
if '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
ways for that to occur
summing the cases we get that the probability for and
to have disjoint ranges is equal to:
so the final answer is