2014 AIME I Problems/Problem 12
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.
Thus, there are ways 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)
Also, 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
There are 4 ways to choose the range of , given by . We then know that each element in can be assigned to only one value, so there are 4 functions with a range of 1 element 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. Thus, there are ways for that to occur
- Summing the cases
We find that the probability of and having disjoint ranges is equal to:
Thus, our final answer is .