3
$\begingroup$

Q. The number of three element sets of positive distinct integers {a, b, c} such that the product abc = 15015 is ?

My approach:-

15015 = 1 * 3 * 5 * 7 * 11 * 13

Now I thought of this problem as 6 distinct balls (1, 3, 5, 7, 11, 13) to be distributed in 3 distinct boxes (a, b, c), such that each box at least have 1 ball in them.

So, I made the following possibilities:-

Case 1:- 3 2 1 ---> $6C3 * 3C2 * 1C1 * 3!$ = 180

Case 2:- 2 2 2 -----> $6C2 * 4C2 * 2C2 $ = 90

Case 3:- 4 1 1 -----> {6C4 * (2C1 * 2C1)/2!} * 3!} = 90

Giving a total of 360 cases, but the answer given is 40, please help me to identify mistake and how to proceed ?

$\endgroup$
4
  • $\begingroup$ Recall that the set $\{1,2,3\}$ is equal as a set to $\{3,1,2\}$. Do not confuse sets with ordered triples. Order does not matter for sets. $\endgroup$
    – JMoravitz
    Commented Nov 9, 2021 at 14:23
  • 4
    $\begingroup$ How do you distinguish between the outcome $\{1\cdot 3\cdot 5, 7\cdot 11, 13\}$ and the outcome $\{3\cdot 5,7\cdot 11,13\cdot 1\}$? Both look like $\{15,77,13\}$ to me. $\endgroup$
    – JMoravitz
    Commented Nov 9, 2021 at 14:25
  • 3
    $\begingroup$ Also, why are you placing the $1$ in a box? It doesn't change the contents of the box. $\endgroup$
    – lulu
    Commented Nov 9, 2021 at 14:28
  • $\begingroup$ How many divisors does $15015$ have ? For how many does the cofactor have $1,2,4,8,16,32$ divisors ? Finally consider how often you counted each combination. $\endgroup$
    – Peter
    Commented Nov 9, 2021 at 14:31

2 Answers 2

8
$\begingroup$

First consider ordered solutions. There are $5$ distinct prime factors. Allocate each one to a slot...that's $3^5$. Now, it's fine if one slot is empty but we don't allow two empty slots (as the three numbers are required to be distinct). Thus we must remove $3$ cases.

Thus we have $3^5-3=240$ ordered solutions. As we can permute any solution in exactly $6$ ways, the answer must be $\frac {240}6=40$.

$\endgroup$
3
  • $\begingroup$ Why are we not considering 1 also , there could be a set with {1, 15, 1001} , and for clarification purposes , the 3 cases which have been subtracted are the ones when all the elements go to first slot (a), second slot (b) or third slot (c) , right ? $\endgroup$
    – Fin27
    Commented Nov 11, 2021 at 7:55
  • $\begingroup$ $1$ corresponds to an empty box. The ordered triple $(1,15,1001)$ would correspond to putting $3,5$ into slot $2$ and all $7,11,13$ into slot $3$. That's why I said one empty slot would be fine, since one $1$ in the triple is allowed. Two empty slots would mean two $1's$ and that is not allowed. $\endgroup$
    – lulu
    Commented Nov 11, 2021 at 11:51
  • $\begingroup$ Should have reminded you: empty products equal $1$, just as empty sums equal $0$. That convention is widely used but if you are unfamiliar with it, just know that it is the convention I am following here. $\endgroup$
    – lulu
    Commented Nov 11, 2021 at 11:56
4
$\begingroup$

Ignore the number $1$ in your analysis. We have the primes $3,5,7,11,13$

We have the possible breakdowns: $4$-$1$-$0$, $3$-$2$-$0$, $3$-$1$-$1$, and $2$-$2$-$1$. Note that $5$-$0$-$0$ doesn't count since this would have resulted in a two element set, not a three.

For the case of $4$-$1$-$0$, pick which element goes for the second batch. $5$ ways.

For the case of $3$-$2$-$0$, pick which three primes go for the first batch... $\binom{5}{3}$. The remaining primes go for the second.

For the case of $3$-$1$-$1$, choose the three primes to go for the first batch. The remaining primes go one each into the others and it doesn't matter which. $\binom{5}{3}$ here again.

For the last case of $2$-$2$-$1$, choose the prime that goes for the $1$. Now... among the remaining four primes one will be smallest and might as well be sent to the first batch. Choose which of the remaining primes goes with that smallest prime. $5\cdot 3$ ways.

$$5+\binom{5}{3}+\binom{5}{3}+5\cdot 3 = 5+10 + 10 + 15 = 40$$

$\endgroup$
6
  • $\begingroup$ Why are we not considering 1 also , there could be a set with {1, 15, 1001} ? and also in the case of 4-1-0 , why shouldn't it be $\binom{5}{4} * \binom{4}{1}$ ? $\endgroup$
    – Fin27
    Commented Nov 11, 2021 at 7:57
  • $\begingroup$ {1,15,1001} was counted in my 3-2-0 case above, the 0 in 3-2-0 corresponding to zero primes being placed in a group together... i.e. what is placed there is the number 1. As for 4-1-0, we first pick four of the primes out of the five to go in the big group. Once those four have been picked... there is only one left to choose from... not four. $\endgroup$
    – JMoravitz
    Commented Nov 11, 2021 at 13:37
  • $\begingroup$ for the case of 2-2-1 , what change should I make to this equation $\binom{5}{2} * \binom{3}{2} * \binom{1}{1}$ , to reach at answer, I understand this contains ordered solutions, like it would contain a case when 1st box has 2 primes , 2nd box has 2 primes and 3rd has 1 prime , also it would include a case where 1st box has 2 primes, 2nd box has 1 prime and 3rd has 2 primes and so on, there would be too many cases out here $\endgroup$
    – Fin27
    Commented Nov 13, 2021 at 23:26
  • $\begingroup$ You need to divide by 2 to "forget" which "2" was which since there shouldn't be a "first 2" compared to the"second 2". Alternatively, do as I suggest above and take advantage of the fact that among the four primes used for the 2's, one of them is smallest and all we need to know is which other prime is paired with it $\endgroup$
    – JMoravitz
    Commented Nov 13, 2021 at 23:34
  • $\begingroup$ why 2 ? I guess it should be more than 2 , we have cases for 2,1,2 ; 2,2,1; 1,2,2 $\endgroup$
    – Fin27
    Commented Nov 14, 2021 at 0:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .