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 12: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. 
