2016 AIME II Problems/Problem 8
Find the number of sets of three distinct positive integers with the property that the product of and is equal to the product of .
Note that the prime factorization of the product is . Ignoring overcounting, by stars and bars there are ways to choose how to distribute the factors of , and ways to distribute the factors of the other primes, so we have ways. However, some sets have numbers that are the same, namely the ones in the form and , which are each counted times, and each other set is counted times, so the desired answer is .
Again, notice that the prime factors of the product are . In this problem, we are asked to partition this set of distinct(ish) factors into three smaller indistinct sets. To do this, we can use Stirling numbers of the second kind, but Stirling numbers of the second kind would assume no empty parts, which isn't what we want. However, this is easy to fix. Denote Stirling numbers of the second kind with . We may start at the situation when all three sets are nonempty. Then, the number of partitions is simply . However, we are overcounting, since every time the two threes are in different sets, (unless they are both individually in their own sets), each one is double counted. To fix this, we can see that they were in different sets times by complementary counting, but one of these times they were in their own individual sets, so the total overcount is . Similarly, we can do the cases for if two of the sets are nonempty and one of the sets are nonempty, (but in those last two cases the threes cannot be individually in their own sets). We then find that the "answer" is given by: Drawing out the Stirling number triangle and evaluating yields for the last expression. However, throughout the entire solution, we ignored the fact that the three numbers , , and needed to be distinct. However, this is easy to fix, since there are only two sets in which they are not, namely and . Thus, the actual answer is .
|2016 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|