Difference between revisions of "2014 AIME I Problems/Problem 12"
(→Solution) |
m (→Solution) |
||
Line 42: | Line 42: | ||
<math>\dfrac{324 + 1344 + 144}{256^2}=\dfrac{1812}{2^{16}}= \dfrac{453}{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>453</math>. | + | Thus, our final answer is <math>\boxed{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 13:42, 15 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 possibilities for each of
and
from
to
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 with range 1, 2, etc.
- Range 1:
There are 4 possibilities: all elements output to 1, 2, 3, or 4.
- Range 2:
We have ways to choose the two output elements for
. At this point we have two possibilities: either
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
ways to rearrange the 4 elements, for a total of
ways for this case. For the second case, there are
ways to rearrange the 4 elements, for a total of
ways for this case. Adding these two, we get a total of
total possibilities.
- Range 3:
We have ways to choose the three output elements for
. 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
ways to rearrange these elements (since we can pick the locations of the 2 single elements in this many ways), and our total is
ways.
- Range 4:
Since we know the elements present, we have ways to arrange them, or 24 ways.
(To check, , which is the total number of possibilities).
We now break down by cases, and count the number of
whose ranges are disjoint from
's.
- Case 1:
's range contains 1 element
We know that there are 3 possibilities for with 1 element. Since half the possibilities for
with two elements will contain the element in
, there are
possibilities for
with 2 elements. Since
the possibilities for
with 3 elements will contain the element in
, there are
possibilities for
with 3 elements. Clearly, no 4-element range for
is possible, so the total number of ways for this case to happen is
.
- Case 2:
's range contains 2 elements
We know that there are 2 possibilities for with 1 element. If
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
is
. No 3-element or 4-element ranges for
are possible. Thus, the total number of ways for this to happen is
.
- Case 3:
's range contains 3 elements
In this case, there is only 1 possibility for - all the output values are the element that does not appear in
's range. Thus, the total number of ways for this to happen is
.
- Summing the cases
We find that the probability of and
having disjoint ranges is equal to:
Thus, our final answer is .
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.