Difference between revisions of "2016 AIME II Problems/Problem 8"
(→Problem) |
|||
| Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
| − | Find the number of sets <math>{a,b,c}</math> of three distinct positive integers with the property that the product of <math>a,b,</math> and <math>c</math> is equal to the product of <math>11,21,31,41,51,61</math>. | + | Find the number of sets <math>\{a,b,c\}</math> of three distinct positive integers with the property that the product of <math>a,b,</math> and <math>c</math> is equal to the product of <math>11,21,31,41,51,61</math>. |
==Solution== | ==Solution== | ||
Latest revision as of 18:02, 7 December 2022
Contents
Problem
Find the number of sets 
of three distinct positive integers with the property that the product of 
and 
is equal to the product of 
.
Solution
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 
.
Solution 2
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:
![\[S(8,3) - \dfrac{S(8,3) - S(7,3) - 1}{2} + S(8,2) - \dfrac{S(8,2) - S(7,2)}{2}+ S(8,1) - \dfrac{S(8,1) - S(7,1)}{2}\]](http://latex.artofproblemsolving.com/c/4/5/c45a4fb1484feca111761435755d90fda458ab11.png)
![\[= \dfrac{S(8,3)+S(8,2) + S(8,1) + S(7,3) + S(7,2) + S(7,1) + 1}{2}\]](http://latex.artofproblemsolving.com/6/4/6/646024c4af67bc9c8c3e50f0553372307d25a96d.png)
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 
.
- Aathreyakadambi
See also
| 2016 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 7 |
Followed by Problem 9 | |
| 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. 
