2014 AIME I Problems/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 1 (casework)
The natural way to go is casework. And the natural process is to sort and based on range size! Via Pigeonhole Principle, we see that the only real possibilities are: . Note that the and cases are symmetrical and we need just a . Note also that the total number of cases is .
: clearly, we choose one number as the range for , one for , yielding possibilities.
with symmetry (WLOG has 1 element): start by selecting numbers for the ranges. This yields for the one number in , and options for the two numbers for . Afterwards, note that the function with 2 numbers in the range can have arrangements of these two numbers (1 of one, 3 of the other *2 and 2 of each). Therefore, we have possibilities, the 2 from symmetry.
: no symmetry, still easy! Just note that we have choices of which numbers go to and , and within each, choices for the orientation of each of the two numbers. That's possibilities.
: again, symmetrical (WLOG has one element): ways to select the single element for , and then find the number of ways to distribute the distinct numbers in the range for . The only arrangement for the frequency of each number is in some order. Therefore, we have ways to choose which number is the one represented twice, and then note that there are ways to arrange these! The number of possibilities in this situation is .
Total, divided by , gets , with numerator .
Solution 2 (casework)
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 .
Solution 3 (simplification of Solution 2)
As before, there are 4 functions with a range of size 1, 84 with a range of size 2, and 144 with a range of size 3. If the range of has size , the codomain of is restricted to a set of size . Any function from into this codomain will do, so there are possibilities for given a function . The probability of and having disjoint ranges is then
|2014 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|