2020 AIME I Problems/Problem 9
Let be the set of positive integer divisors of Three numbers are chosen independently and at random with replacement from the set and labeled and in the order they are chosen. The probability that both divides and divides is where and are relatively prime positive integers. Find
First, prime factorize as . Denote as , as , and as .
In order for to divide , and for to divide , , and . We will consider each case separately. Note that the total amount of possibilities is , as there are choices for each factor.
We notice that if we add to and to , then we can reach the stronger inequality . Therefore, if we pick integers from to , they will correspond to a unique solution, forming a 1-1 correspondence between the numbers , , and . This is also equivalent to applying stars and bars on distributing the powers of 2 and 5 through differences. The amount of solutions to this inequality is .
The case for ,, and proceeds similarly for a result of . Therefore, the probability of choosing three such factors is Simplification gives , and therefore the answer is .
Same as before, say the factors have powers of and . can either be all distinct, all equal, or two of the three are equal. As well, we must have . If they are all distinct, the number of cases is simply . If they are all equal, there are only cases for the general value. If we have a pair equal, then we have . We need to multiply by because if we have two values , we can have either or .
Likewise for , we get
The final probability is simply . Simplification gives , and therefore the answer is .
|2020 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|