Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 AIME II Problems/Problem 8"
Line 5: Line 5:
 
Note that the prime factorization of the product is <math>3^{2}\cdot 7 \cdot 11 \cdot 17 \cdot 31 \cdot 41 \cdot 61</math>. Ignoring overcounting, by stars and bars there are <math>6</math> ways to choose how to distribute the factors of <math>3</math>, and <math>3</math> ways to distribute the factors of the other primes, so we have <math>3^{6} \cdot 6</math> ways. However, some sets have <math>2</math> numbers that are the same, namely the ones in the form <math>1,1,x</math> and <math>3,3,x</math>, which are each counted <math>3</math> times, and each other set is counted <math>6</math> times, so the desired answer is <math>\dfrac{729 \cdot 6-6}{6} = \boxed{728}</math>.
 
Note that the prime factorization of the product is <math>3^{2}\cdot 7 \cdot 11 \cdot 17 \cdot 31 \cdot 41 \cdot 61</math>. Ignoring overcounting, by stars and bars there are <math>6</math> ways to choose how to distribute the factors of <math>3</math>, and <math>3</math> ways to distribute the factors of the other primes, so we have <math>3^{6} \cdot 6</math> ways. However, some sets have <math>2</math> numbers that are the same, namely the ones in the form <math>1,1,x</math> and <math>3,3,x</math>, which are each counted <math>3</math> times, and each other set is counted <math>6</math> times, so the desired answer is <math>\dfrac{729 \cdot 6-6}{6} = \boxed{728}</math>.
  
−
Solution by Shaddoll
 
  
 
==Solution 2==
 
==Solution 2==

Revision as of 18:57, 18 October 2020

Problem

Find the number of sets ${a,b,c}$ of three distinct positive integers with the property that the product of $a,b,$ and $c$ is equal to the product of $11,21,31,41,51,61$.

Solution

Note that the prime factorization of the product is $3^{2}\cdot 7 \cdot 11 \cdot 17 \cdot 31 \cdot 41 \cdot 61$. Ignoring overcounting, by stars and bars there are $6$ ways to choose how to distribute the factors of $3$, and $3$ ways to distribute the factors of the other primes, so we have $3^{6} \cdot 6$ ways. However, some sets have $2$ numbers that are the same, namely the ones in the form $1,1,x$ and $3,3,x$, which are each counted $3$ times, and each other set is counted $6$ times, so the desired answer is $\dfrac{729 \cdot 6-6}{6} = \boxed{728}$.


Solution 2

Again, notice that the prime factors of the product are $3, 3, 7, 11, 17, 31, 41, 61$. 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 $S(n,k)$. We may start at the situation when all three sets are nonempty. Then, the number of partitions is simply $S(8,3)$. 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 $S(8, 3) - S(7,3)$ times by complementary counting, but one of these times they were in their own individual sets, so the total overcount is $\dfrac{S(8,3) - S(7,3) - 1}{2}$. 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}\] \[= \dfrac{S(8,3)+S(8,2) + S(8,1) + S(7,3) + S(7,2) + S(7,1) + 1}{2}\] Drawing out the Stirling number triangle and evaluating yields $730$ for the last expression. However, throughout the entire solution, we ignored the fact that the three numbers $a$, $b$, and $c$ needed to be distinct. However, this is easy to fix, since there are only two sets in which they are not, namely $(1,1,x)$ and $(3,3,x)$. Thus, the actual answer is $730 - 2 = \boxed{728}$.

- 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_AIME_II_Problems/Problem_8&oldid=135256"