Mixing
How many ways to write one million as a product of three positive integers?
$begingroup$
In how many ways can the number 1;000;000 (one million) be written as the product
of three positive integers $a, b, c,$ where $a le b le c$?
(A) 139
(B) 196
(C) 219
(D) 784
(E) None of the above
This is my working out so far:
$1000000 = 10^{6} = 2^{6} cdot 5^{6}$ and then to consider this as the product of three factors i.e.
$10^6 = 2^6 cdot 5^6$
$= 2^a 5^p cdot 2^b5^q cdot 2^c 5^r$ (where $a+b+c = 6$ and $p+q+r = 6$).
However there are repetitions here because $2^3,5^3 cdot 2^2,5^2 cdot 2^1,5^1$ is the product of the same three factors as $2^2,5^2 cdot 2^3,5^3 cdot 2^1,5^1$.
I think there are 139 such factors.
combinatorics number-theory recreational-mathematics
edited Jan 9 at 11:55
bof
51.4k557120
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
$endgroup$
add a comment |
$begingroup$
In how many ways can the number 1;000;000 (one million) be written as the product
of three positive integers $a, b, c,$ where $a le b le c$?
(A) 139
(B) 196
(C) 219
(D) 784
(E) None of the above
This is my working out so far:
$1000000 = 10^{6} = 2^{6} cdot 5^{6}$ and then to consider this as the product of three factors i.e.
$10^6 = 2^6 cdot 5^6$
$= 2^a 5^p cdot 2^b5^q cdot 2^c 5^r$ (where $a+b+c = 6$ and $p+q+r = 6$).
However there are repetitions here because $2^3,5^3 cdot 2^2,5^2 cdot 2^1,5^1$ is the product of the same three factors as $2^2,5^2 cdot 2^3,5^3 cdot 2^1,5^1$.
I think there are 139 such factors.
combinatorics number-theory recreational-mathematics
edited Jan 9 at 11:55
bof
51.4k557120
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
$endgroup$
2
$begingroup$
I think some working or demonstration of effort should be given. As a very general comment, this kind of problem calls for some careful organisation of cases - so some clarity of thought. It is worth trying this out for yourself before asking for help, because it always looks so blindingly obvious when you are told a good way of doing it - and that doesn't do anything much to help you solve the next problem.
$endgroup$
– Mark Bennet
Jan 8 '13 at 23:17
$begingroup$
Sorry didn't have time to write my working out beforehand, just came back to write my working out now.
$endgroup$
– DeeDee
Jan 8 '13 at 23:35
add a comment |
$begingroup$
In how many ways can the number 1;000;000 (one million) be written as the product
of three positive integers $a, b, c,$ where $a le b le c$?
(A) 139
(B) 196
(C) 219
(D) 784
(E) None of the above
This is my working out so far:
$1000000 = 10^{6} = 2^{6} cdot 5^{6}$ and then to consider this as the product of three factors i.e.
$10^6 = 2^6 cdot 5^6$
$= 2^a 5^p cdot 2^b5^q cdot 2^c 5^r$ (where $a+b+c = 6$ and $p+q+r = 6$).
However there are repetitions here because $2^3,5^3 cdot 2^2,5^2 cdot 2^1,5^1$ is the product of the same three factors as $2^2,5^2 cdot 2^3,5^3 cdot 2^1,5^1$.
I think there are 139 such factors.
combinatorics number-theory recreational-mathematics
edited Jan 9 at 11:55
bof
51.4k557120
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
$endgroup$
In how many ways can the number 1;000;000 (one million) be written as the product
of three positive integers $a, b, c,$ where $a le b le c$?
(A) 139
(B) 196
(C) 219
(D) 784
(E) None of the above
This is my working out so far:
$1000000 = 10^{6} = 2^{6} cdot 5^{6}$ and then to consider this as the product of three factors i.e.
$10^6 = 2^6 cdot 5^6$
$= 2^a 5^p cdot 2^b5^q cdot 2^c 5^r$ (where $a+b+c = 6$ and $p+q+r = 6$).
However there are repetitions here because $2^3,5^3 cdot 2^2,5^2 cdot 2^1,5^1$ is the product of the same three factors as $2^2,5^2 cdot 2^3,5^3 cdot 2^1,5^1$.
I think there are 139 such factors.
combinatorics number-theory recreational-mathematics
combinatorics number-theory recreational-mathematics
edited Jan 9 at 11:55
bof
51.4k557120
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
edited Jan 9 at 11:55
bof
51.4k557120
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
edited Jan 9 at 11:55
bof
51.4k557120
edited Jan 9 at 11:55
bof
51.4k557120
edited Jan 9 at 11:55
bof
51.4k557120
51.4k557120
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
asked Jan 8 '13 at 22:35
DeeDeeDeeDee
278
278
2
$begingroup$
I think some working or demonstration of effort should be given. As a very general comment, this kind of problem calls for some careful organisation of cases - so some clarity of thought. It is worth trying this out for yourself before asking for help, because it always looks so blindingly obvious when you are told a good way of doing it - and that doesn't do anything much to help you solve the next problem.
$endgroup$
– Mark Bennet
Jan 8 '13 at 23:17
$begingroup$
Sorry didn't have time to write my working out beforehand, just came back to write my working out now.
$endgroup$
– DeeDee
Jan 8 '13 at 23:35
add a comment |
2
$begingroup$
I think some working or demonstration of effort should be given. As a very general comment, this kind of problem calls for some careful organisation of cases - so some clarity of thought. It is worth trying this out for yourself before asking for help, because it always looks so blindingly obvious when you are told a good way of doing it - and that doesn't do anything much to help you solve the next problem.
$endgroup$
– Mark Bennet
Jan 8 '13 at 23:17
$begingroup$
Sorry didn't have time to write my working out beforehand, just came back to write my working out now.
$endgroup$
– DeeDee
Jan 8 '13 at 23:35
2
2
$begingroup$
I think some working or demonstration of effort should be given. As a very general comment, this kind of problem calls for some careful organisation of cases - so some clarity of thought. It is worth trying this out for yourself before asking for help, because it always looks so blindingly obvious when you are told a good way of doing it - and that doesn't do anything much to help you solve the next problem.
$endgroup$
– Mark Bennet
Jan 8 '13 at 23:17
$begingroup$
I think some working or demonstration of effort should be given. As a very general comment, this kind of problem calls for some careful organisation of cases - so some clarity of thought. It is worth trying this out for yourself before asking for help, because it always looks so blindingly obvious when you are told a good way of doing it - and that doesn't do anything much to help you solve the next problem.
$endgroup$
– Mark Bennet
Jan 8 '13 at 23:17
$begingroup$
Sorry didn't have time to write my working out beforehand, just came back to write my working out now.
$endgroup$
– DeeDee
Jan 8 '13 at 23:35
$begingroup$
Sorry didn't have time to write my working out beforehand, just came back to write my working out now.
$endgroup$
– DeeDee
Jan 8 '13 at 23:35
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Hint: Solve the problem for $abc = 10^6$. This has $ {8 choose 2}^2=784$ solutions.
Count the number of solutions where $a=b=c$.
Count the number of solutions where $a=b$ or $b=c$ or $c=a$.
Count the number of solutions where $a, b, c$ are pairwise distinct.
Account for your repeated counting above, to find the cases where $a leq b leq c$.
Motivation: Bars and stripes, Orbit Stabilizier Theorem.
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
$endgroup$
$begingroup$
My friend tried using combinations of factors. 1 x 1 x 1000000, 1 x 2 x 500000, 1 x 4 x 250000, ... ... 80 x 100 x 125, 100 x 100 x 100.
$endgroup$
– DeeDee
Jan 8 '13 at 23:55
1
$begingroup$
@user55613 I designed this problem for Brilliant.org, though it's basic enough that you could conceivably find it elsewhere, which is why I withdrew my objection. The above is a straightforward approach to work on this very easily, having understood the effects of double counting. Of course, listing out all the factors is one brute force way to do it, but it doesn't add to your understanding of the issues at hand.
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:57
$begingroup$
@CalvinLin: furthermore, this question counts $1cdot2^6cdot5^6$ and $2^6cdot1cdot5^6$ as the same, whereas the brilliand.org question counts them as different (as asked).
$endgroup$
– robjohn♦
Jan 9 '13 at 0:17
$begingroup$
@robjohn I had a version that was the same as this, but responded before I checked that I sent the correct link. OP mentioned that this is MCQ, which will be very different from a short answer qn, which is why I withdrew my objection (deleted comments, but couldn't pull chat or flag). I gave an explanation of an approach that is logical, and not simply brute force / coded, so that even if someone sees this, they do not get the answer directly, but have to work through it and understand what is happening.
$endgroup$
– Calvin Lin
Jan 9 '13 at 0:23
add a comment |
$begingroup$
As we can factorise one million as $5^6 times 2^6 $, it becomes a matter of how many ways we can split up a set of size 12 into three disjoint subsets. This is more of a combinatronics problem, really.
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
$endgroup$
$begingroup$
I don't understand the downvote. This answer is exactly headed in the right directly. Of course, it misses the detail of keeping track of repetitions.
$endgroup$
– Code-Guru
Jan 8 '13 at 22:59
$begingroup$
This is not true. Perhaps if it's 2 sets of size 6, split into 3 disjoint subsets, AND then keeping track of repetitions
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:00
$begingroup$
Yeah, I forgot about the fact we'd be counting extra numbers of numbers (we'd be counting three for every one we need, I believe, although this is a quick guess) - as for the 2 sets of size 6, I fail to see why this is any different to one set of size 12 (as the 2 sets of size 6 will be disjoint).
$endgroup$
– Andrew D
Jan 8 '13 at 23:03
$begingroup$
Actually, now I've had a proper look at it, I can see why having 2 sets of size 6 is useful - it cuts down on a lot of repetitions doing it with a set of size 12.
$endgroup$
– Andrew D
Jan 8 '13 at 23:20
add a comment |
$begingroup$
The problem can be reduced to finding the set X of ordered pair of triplets (xyz, pqr) providing $x+y+z=p+q+r=6$ and $2^x5^pleq2^y5^qleq2^z5^r$(to avoid repetition), then the size of X is the answer.
There are 7 triplets(ignoring order) that sum up to 6:
006, 015, 024, 033, 114, 123, 222
As order in the triplets matters((xyz, xyz), (xyz, xzy) etc are distinct), we can not simply find X by squaring of the set of these 7 triplets. Even squaring the set of 28 variants of the 7 triplets ($3*P(3, 3)+3*P(3,1)+1=28$) doesn't resolves to $X$. Because (xyz, xyz), (zyx, zyx) etc are distinct.
Now classifying the 7 triplets into 3 groups may help:
- no-repeat group: 123; 015; 024;
- 2-repeat group: 006; 330; 114;
- 3-repeat group: 222;
Consider the following observations
6 pairs can be made with a no-repeat triplet xyz i.e. a triplet of
the no-repeat group.
To demonstrate, (123, 123), (123, 132),
(123, 213), (123, 231), (123, 312), (123, 321) pairs can be made
with the triplet 123. As these 6 pairs represent 6 unique way to
express $10^6$($10*100*1000$, $10*500*200$, ...) the no repetition
rule($aleq bleq c$) has been followed.
6 pairs can be made with two no-repeat triplet xyz
and pqr(actually 12 pairs if we alternate the order of the pairs but we will
consider that manually in calculation).
2 pairs can be made with a 2-repeat triplet xxy.
2 pairs can be made with two 2-r triplet xxy and ppq or xyy and xpp(consider every case).
3 pairs can be made with xyz and ppq. The pairs are (xyz, ppq), (xyz, pqp), (xyz, qpp). Alternating the order makes 3 more pairs so we have to multiply the result by 2(see |C| below).- Only 1 pair can be made with xxx and xxx, pqr, mmn.
Now let A, B, C, D be four disjoint subset of X where,
$A$ contains only pairs of no-repeat triplets
$B$ contains only pairs of 2-repeat triplets
$C$ contains pairs of one no-repeat and one 2-repeat triplets
$D$ contains All pairs with at most one 3-repeat triplet
So, $Acup Bcup Ccup D=X$
$|A|=3^2*6$
$|B|=3^2*2$
$|C|=2*3^2*3$
$|D|=1+2*(3+3)$
So the answer is $3^2*6+3^2*2+2*3^2*3+1+2*(3+3)=139$
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f273137%2fhow-many-ways-to-write-one-million-as-a-product-of-three-positive-integers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint: Solve the problem for $abc = 10^6$. This has $ {8 choose 2}^2=784$ solutions.
Count the number of solutions where $a=b=c$.
Count the number of solutions where $a=b$ or $b=c$ or $c=a$.
Count the number of solutions where $a, b, c$ are pairwise distinct.
Account for your repeated counting above, to find the cases where $a leq b leq c$.
Motivation: Bars and stripes, Orbit Stabilizier Theorem.
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
$endgroup$
$begingroup$
My friend tried using combinations of factors. 1 x 1 x 1000000, 1 x 2 x 500000, 1 x 4 x 250000, ... ... 80 x 100 x 125, 100 x 100 x 100.
$endgroup$
– DeeDee
Jan 8 '13 at 23:55
1
$begingroup$
@user55613 I designed this problem for Brilliant.org, though it's basic enough that you could conceivably find it elsewhere, which is why I withdrew my objection. The above is a straightforward approach to work on this very easily, having understood the effects of double counting. Of course, listing out all the factors is one brute force way to do it, but it doesn't add to your understanding of the issues at hand.
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:57
$begingroup$
@CalvinLin: furthermore, this question counts $1cdot2^6cdot5^6$ and $2^6cdot1cdot5^6$ as the same, whereas the brilliand.org question counts them as different (as asked).
$endgroup$
– robjohn♦
Jan 9 '13 at 0:17
$begingroup$
@robjohn I had a version that was the same as this, but responded before I checked that I sent the correct link. OP mentioned that this is MCQ, which will be very different from a short answer qn, which is why I withdrew my objection (deleted comments, but couldn't pull chat or flag). I gave an explanation of an approach that is logical, and not simply brute force / coded, so that even if someone sees this, they do not get the answer directly, but have to work through it and understand what is happening.
$endgroup$
– Calvin Lin
Jan 9 '13 at 0:23
add a comment |
$begingroup$
Hint: Solve the problem for $abc = 10^6$. This has $ {8 choose 2}^2=784$ solutions.
Count the number of solutions where $a=b=c$.
Count the number of solutions where $a=b$ or $b=c$ or $c=a$.
Count the number of solutions where $a, b, c$ are pairwise distinct.
Account for your repeated counting above, to find the cases where $a leq b leq c$.
Motivation: Bars and stripes, Orbit Stabilizier Theorem.
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
$endgroup$
$begingroup$
My friend tried using combinations of factors. 1 x 1 x 1000000, 1 x 2 x 500000, 1 x 4 x 250000, ... ... 80 x 100 x 125, 100 x 100 x 100.
$endgroup$
– DeeDee
Jan 8 '13 at 23:55
1
$begingroup$
@user55613 I designed this problem for Brilliant.org, though it's basic enough that you could conceivably find it elsewhere, which is why I withdrew my objection. The above is a straightforward approach to work on this very easily, having understood the effects of double counting. Of course, listing out all the factors is one brute force way to do it, but it doesn't add to your understanding of the issues at hand.
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:57
$begingroup$
@CalvinLin: furthermore, this question counts $1cdot2^6cdot5^6$ and $2^6cdot1cdot5^6$ as the same, whereas the brilliand.org question counts them as different (as asked).
$endgroup$
– robjohn♦
Jan 9 '13 at 0:17
$begingroup$
@robjohn I had a version that was the same as this, but responded before I checked that I sent the correct link. OP mentioned that this is MCQ, which will be very different from a short answer qn, which is why I withdrew my objection (deleted comments, but couldn't pull chat or flag). I gave an explanation of an approach that is logical, and not simply brute force / coded, so that even if someone sees this, they do not get the answer directly, but have to work through it and understand what is happening.
$endgroup$
– Calvin Lin
Jan 9 '13 at 0:23
add a comment |
$begingroup$
Hint: Solve the problem for $abc = 10^6$. This has $ {8 choose 2}^2=784$ solutions.
Count the number of solutions where $a=b=c$.
Count the number of solutions where $a=b$ or $b=c$ or $c=a$.
Count the number of solutions where $a, b, c$ are pairwise distinct.
Account for your repeated counting above, to find the cases where $a leq b leq c$.
Motivation: Bars and stripes, Orbit Stabilizier Theorem.
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
$endgroup$
Hint: Solve the problem for $abc = 10^6$. This has $ {8 choose 2}^2=784$ solutions.
Count the number of solutions where $a=b=c$.
Count the number of solutions where $a=b$ or $b=c$ or $c=a$.
Count the number of solutions where $a, b, c$ are pairwise distinct.
Account for your repeated counting above, to find the cases where $a leq b leq c$.
Motivation: Bars and stripes, Orbit Stabilizier Theorem.
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
answered Jan 8 '13 at 23:41
Calvin LinCalvin Lin
36.3k349114
36.3k349114
$begingroup$
My friend tried using combinations of factors. 1 x 1 x 1000000, 1 x 2 x 500000, 1 x 4 x 250000, ... ... 80 x 100 x 125, 100 x 100 x 100.
$endgroup$
– DeeDee
Jan 8 '13 at 23:55
1
$begingroup$
@user55613 I designed this problem for Brilliant.org, though it's basic enough that you could conceivably find it elsewhere, which is why I withdrew my objection. The above is a straightforward approach to work on this very easily, having understood the effects of double counting. Of course, listing out all the factors is one brute force way to do it, but it doesn't add to your understanding of the issues at hand.
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:57
$begingroup$
@CalvinLin: furthermore, this question counts $1cdot2^6cdot5^6$ and $2^6cdot1cdot5^6$ as the same, whereas the brilliand.org question counts them as different (as asked).
$endgroup$
– robjohn♦
Jan 9 '13 at 0:17
$begingroup$
@robjohn I had a version that was the same as this, but responded before I checked that I sent the correct link. OP mentioned that this is MCQ, which will be very different from a short answer qn, which is why I withdrew my objection (deleted comments, but couldn't pull chat or flag). I gave an explanation of an approach that is logical, and not simply brute force / coded, so that even if someone sees this, they do not get the answer directly, but have to work through it and understand what is happening.
$endgroup$
– Calvin Lin
Jan 9 '13 at 0:23
add a comment |
$begingroup$
My friend tried using combinations of factors. 1 x 1 x 1000000, 1 x 2 x 500000, 1 x 4 x 250000, ... ... 80 x 100 x 125, 100 x 100 x 100.
$endgroup$
– DeeDee
Jan 8 '13 at 23:55
1
$begingroup$
@user55613 I designed this problem for Brilliant.org, though it's basic enough that you could conceivably find it elsewhere, which is why I withdrew my objection. The above is a straightforward approach to work on this very easily, having understood the effects of double counting. Of course, listing out all the factors is one brute force way to do it, but it doesn't add to your understanding of the issues at hand.
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:57
$begingroup$
@CalvinLin: furthermore, this question counts $1cdot2^6cdot5^6$ and $2^6cdot1cdot5^6$ as the same, whereas the brilliand.org question counts them as different (as asked).
$endgroup$
– robjohn♦
Jan 9 '13 at 0:17
$begingroup$
@robjohn I had a version that was the same as this, but responded before I checked that I sent the correct link. OP mentioned that this is MCQ, which will be very different from a short answer qn, which is why I withdrew my objection (deleted comments, but couldn't pull chat or flag). I gave an explanation of an approach that is logical, and not simply brute force / coded, so that even if someone sees this, they do not get the answer directly, but have to work through it and understand what is happening.
$endgroup$
– Calvin Lin
Jan 9 '13 at 0:23
$begingroup$
My friend tried using combinations of factors. 1 x 1 x 1000000, 1 x 2 x 500000, 1 x 4 x 250000, ... ... 80 x 100 x 125, 100 x 100 x 100.
$endgroup$
– DeeDee
Jan 8 '13 at 23:55
$begingroup$
My friend tried using combinations of factors. 1 x 1 x 1000000, 1 x 2 x 500000, 1 x 4 x 250000, ... ... 80 x 100 x 125, 100 x 100 x 100.
$endgroup$
– DeeDee
Jan 8 '13 at 23:55
1
1
$begingroup$
@user55613 I designed this problem for Brilliant.org, though it's basic enough that you could conceivably find it elsewhere, which is why I withdrew my objection. The above is a straightforward approach to work on this very easily, having understood the effects of double counting. Of course, listing out all the factors is one brute force way to do it, but it doesn't add to your understanding of the issues at hand.
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:57
$begingroup$
@user55613 I designed this problem for Brilliant.org, though it's basic enough that you could conceivably find it elsewhere, which is why I withdrew my objection. The above is a straightforward approach to work on this very easily, having understood the effects of double counting. Of course, listing out all the factors is one brute force way to do it, but it doesn't add to your understanding of the issues at hand.
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:57
$begingroup$
@CalvinLin: furthermore, this question counts $1cdot2^6cdot5^6$ and $2^6cdot1cdot5^6$ as the same, whereas the brilliand.org question counts them as different (as asked).
$endgroup$
– robjohn♦
Jan 9 '13 at 0:17
$begingroup$
@CalvinLin: furthermore, this question counts $1cdot2^6cdot5^6$ and $2^6cdot1cdot5^6$ as the same, whereas the brilliand.org question counts them as different (as asked).
$endgroup$
– robjohn♦
Jan 9 '13 at 0:17
$begingroup$
@robjohn I had a version that was the same as this, but responded before I checked that I sent the correct link. OP mentioned that this is MCQ, which will be very different from a short answer qn, which is why I withdrew my objection (deleted comments, but couldn't pull chat or flag). I gave an explanation of an approach that is logical, and not simply brute force / coded, so that even if someone sees this, they do not get the answer directly, but have to work through it and understand what is happening.
$endgroup$
– Calvin Lin
Jan 9 '13 at 0:23
$begingroup$
@robjohn I had a version that was the same as this, but responded before I checked that I sent the correct link. OP mentioned that this is MCQ, which will be very different from a short answer qn, which is why I withdrew my objection (deleted comments, but couldn't pull chat or flag). I gave an explanation of an approach that is logical, and not simply brute force / coded, so that even if someone sees this, they do not get the answer directly, but have to work through it and understand what is happening.
$endgroup$
– Calvin Lin
Jan 9 '13 at 0:23
add a comment |
$begingroup$
As we can factorise one million as $5^6 times 2^6 $, it becomes a matter of how many ways we can split up a set of size 12 into three disjoint subsets. This is more of a combinatronics problem, really.
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
$endgroup$
$begingroup$
I don't understand the downvote. This answer is exactly headed in the right directly. Of course, it misses the detail of keeping track of repetitions.
$endgroup$
– Code-Guru
Jan 8 '13 at 22:59
$begingroup$
This is not true. Perhaps if it's 2 sets of size 6, split into 3 disjoint subsets, AND then keeping track of repetitions
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:00
$begingroup$
Yeah, I forgot about the fact we'd be counting extra numbers of numbers (we'd be counting three for every one we need, I believe, although this is a quick guess) - as for the 2 sets of size 6, I fail to see why this is any different to one set of size 12 (as the 2 sets of size 6 will be disjoint).
$endgroup$
– Andrew D
Jan 8 '13 at 23:03
$begingroup$
Actually, now I've had a proper look at it, I can see why having 2 sets of size 6 is useful - it cuts down on a lot of repetitions doing it with a set of size 12.
$endgroup$
– Andrew D
Jan 8 '13 at 23:20
add a comment |
$begingroup$
As we can factorise one million as $5^6 times 2^6 $, it becomes a matter of how many ways we can split up a set of size 12 into three disjoint subsets. This is more of a combinatronics problem, really.
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
$endgroup$
$begingroup$
I don't understand the downvote. This answer is exactly headed in the right directly. Of course, it misses the detail of keeping track of repetitions.
$endgroup$
– Code-Guru
Jan 8 '13 at 22:59
$begingroup$
This is not true. Perhaps if it's 2 sets of size 6, split into 3 disjoint subsets, AND then keeping track of repetitions
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:00
$begingroup$
Yeah, I forgot about the fact we'd be counting extra numbers of numbers (we'd be counting three for every one we need, I believe, although this is a quick guess) - as for the 2 sets of size 6, I fail to see why this is any different to one set of size 12 (as the 2 sets of size 6 will be disjoint).
$endgroup$
– Andrew D
Jan 8 '13 at 23:03
$begingroup$
Actually, now I've had a proper look at it, I can see why having 2 sets of size 6 is useful - it cuts down on a lot of repetitions doing it with a set of size 12.
$endgroup$
– Andrew D
Jan 8 '13 at 23:20
add a comment |
$begingroup$
As we can factorise one million as $5^6 times 2^6 $, it becomes a matter of how many ways we can split up a set of size 12 into three disjoint subsets. This is more of a combinatronics problem, really.
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
$endgroup$
As we can factorise one million as $5^6 times 2^6 $, it becomes a matter of how many ways we can split up a set of size 12 into three disjoint subsets. This is more of a combinatronics problem, really.
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
answered Jan 8 '13 at 22:42
Andrew DAndrew D
1,776931
1,776931
$begingroup$
I don't understand the downvote. This answer is exactly headed in the right directly. Of course, it misses the detail of keeping track of repetitions.
$endgroup$
– Code-Guru
Jan 8 '13 at 22:59
$begingroup$
This is not true. Perhaps if it's 2 sets of size 6, split into 3 disjoint subsets, AND then keeping track of repetitions
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:00
$begingroup$
Yeah, I forgot about the fact we'd be counting extra numbers of numbers (we'd be counting three for every one we need, I believe, although this is a quick guess) - as for the 2 sets of size 6, I fail to see why this is any different to one set of size 12 (as the 2 sets of size 6 will be disjoint).
$endgroup$
– Andrew D
Jan 8 '13 at 23:03
$begingroup$
Actually, now I've had a proper look at it, I can see why having 2 sets of size 6 is useful - it cuts down on a lot of repetitions doing it with a set of size 12.
$endgroup$
– Andrew D
Jan 8 '13 at 23:20
add a comment |
$begingroup$
I don't understand the downvote. This answer is exactly headed in the right directly. Of course, it misses the detail of keeping track of repetitions.
$endgroup$
– Code-Guru
Jan 8 '13 at 22:59
$begingroup$
This is not true. Perhaps if it's 2 sets of size 6, split into 3 disjoint subsets, AND then keeping track of repetitions
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:00
$begingroup$
Yeah, I forgot about the fact we'd be counting extra numbers of numbers (we'd be counting three for every one we need, I believe, although this is a quick guess) - as for the 2 sets of size 6, I fail to see why this is any different to one set of size 12 (as the 2 sets of size 6 will be disjoint).
$endgroup$
– Andrew D
Jan 8 '13 at 23:03
$begingroup$
Actually, now I've had a proper look at it, I can see why having 2 sets of size 6 is useful - it cuts down on a lot of repetitions doing it with a set of size 12.
$endgroup$
– Andrew D
Jan 8 '13 at 23:20
$begingroup$
I don't understand the downvote. This answer is exactly headed in the right directly. Of course, it misses the detail of keeping track of repetitions.
$endgroup$
– Code-Guru
Jan 8 '13 at 22:59
$begingroup$
I don't understand the downvote. This answer is exactly headed in the right directly. Of course, it misses the detail of keeping track of repetitions.
$endgroup$
– Code-Guru
Jan 8 '13 at 22:59
$begingroup$
This is not true. Perhaps if it's 2 sets of size 6, split into 3 disjoint subsets, AND then keeping track of repetitions
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:00
$begingroup$
This is not true. Perhaps if it's 2 sets of size 6, split into 3 disjoint subsets, AND then keeping track of repetitions
$endgroup$
– Calvin Lin
Jan 8 '13 at 23:00
$begingroup$
Yeah, I forgot about the fact we'd be counting extra numbers of numbers (we'd be counting three for every one we need, I believe, although this is a quick guess) - as for the 2 sets of size 6, I fail to see why this is any different to one set of size 12 (as the 2 sets of size 6 will be disjoint).
$endgroup$
– Andrew D
Jan 8 '13 at 23:03
$begingroup$
Yeah, I forgot about the fact we'd be counting extra numbers of numbers (we'd be counting three for every one we need, I believe, although this is a quick guess) - as for the 2 sets of size 6, I fail to see why this is any different to one set of size 12 (as the 2 sets of size 6 will be disjoint).
$endgroup$
– Andrew D
Jan 8 '13 at 23:03
$begingroup$
Actually, now I've had a proper look at it, I can see why having 2 sets of size 6 is useful - it cuts down on a lot of repetitions doing it with a set of size 12.
$endgroup$
– Andrew D
Jan 8 '13 at 23:20
$begingroup$
Actually, now I've had a proper look at it, I can see why having 2 sets of size 6 is useful - it cuts down on a lot of repetitions doing it with a set of size 12.
$endgroup$
– Andrew D
Jan 8 '13 at 23:20
add a comment |
$begingroup$
The problem can be reduced to finding the set X of ordered pair of triplets (xyz, pqr) providing $x+y+z=p+q+r=6$ and $2^x5^pleq2^y5^qleq2^z5^r$(to avoid repetition), then the size of X is the answer.
There are 7 triplets(ignoring order) that sum up to 6:
006, 015, 024, 033, 114, 123, 222
As order in the triplets matters((xyz, xyz), (xyz, xzy) etc are distinct), we can not simply find X by squaring of the set of these 7 triplets. Even squaring the set of 28 variants of the 7 triplets ($3*P(3, 3)+3*P(3,1)+1=28$) doesn't resolves to $X$. Because (xyz, xyz), (zyx, zyx) etc are distinct.
Now classifying the 7 triplets into 3 groups may help:
- no-repeat group: 123; 015; 024;
- 2-repeat group: 006; 330; 114;
- 3-repeat group: 222;
Consider the following observations
6 pairs can be made with a no-repeat triplet xyz i.e. a triplet of
the no-repeat group.
To demonstrate, (123, 123), (123, 132),
(123, 213), (123, 231), (123, 312), (123, 321) pairs can be made
with the triplet 123. As these 6 pairs represent 6 unique way to
express $10^6$($10*100*1000$, $10*500*200$, ...) the no repetition
rule($aleq bleq c$) has been followed.
6 pairs can be made with two no-repeat triplet xyz
and pqr(actually 12 pairs if we alternate the order of the pairs but we will
consider that manually in calculation).
2 pairs can be made with a 2-repeat triplet xxy.
2 pairs can be made with two 2-r triplet xxy and ppq or xyy and xpp(consider every case).
3 pairs can be made with xyz and ppq. The pairs are (xyz, ppq), (xyz, pqp), (xyz, qpp). Alternating the order makes 3 more pairs so we have to multiply the result by 2(see |C| below).- Only 1 pair can be made with xxx and xxx, pqr, mmn.
Now let A, B, C, D be four disjoint subset of X where,
$A$ contains only pairs of no-repeat triplets
$B$ contains only pairs of 2-repeat triplets
$C$ contains pairs of one no-repeat and one 2-repeat triplets
$D$ contains All pairs with at most one 3-repeat triplet
So, $Acup Bcup Ccup D=X$
$|A|=3^2*6$
$|B|=3^2*2$
$|C|=2*3^2*3$
$|D|=1+2*(3+3)$
So the answer is $3^2*6+3^2*2+2*3^2*3+1+2*(3+3)=139$
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
$endgroup$
add a comment |
$begingroup$
The problem can be reduced to finding the set X of ordered pair of triplets (xyz, pqr) providing $x+y+z=p+q+r=6$ and $2^x5^pleq2^y5^qleq2^z5^r$(to avoid repetition), then the size of X is the answer.
There are 7 triplets(ignoring order) that sum up to 6:
006, 015, 024, 033, 114, 123, 222
As order in the triplets matters((xyz, xyz), (xyz, xzy) etc are distinct), we can not simply find X by squaring of the set of these 7 triplets. Even squaring the set of 28 variants of the 7 triplets ($3*P(3, 3)+3*P(3,1)+1=28$) doesn't resolves to $X$. Because (xyz, xyz), (zyx, zyx) etc are distinct.
Now classifying the 7 triplets into 3 groups may help:
- no-repeat group: 123; 015; 024;
- 2-repeat group: 006; 330; 114;
- 3-repeat group: 222;
Consider the following observations
6 pairs can be made with a no-repeat triplet xyz i.e. a triplet of
the no-repeat group.
To demonstrate, (123, 123), (123, 132),
(123, 213), (123, 231), (123, 312), (123, 321) pairs can be made
with the triplet 123. As these 6 pairs represent 6 unique way to
express $10^6$($10*100*1000$, $10*500*200$, ...) the no repetition
rule($aleq bleq c$) has been followed.
6 pairs can be made with two no-repeat triplet xyz
and pqr(actually 12 pairs if we alternate the order of the pairs but we will
consider that manually in calculation).
2 pairs can be made with a 2-repeat triplet xxy.
2 pairs can be made with two 2-r triplet xxy and ppq or xyy and xpp(consider every case).
3 pairs can be made with xyz and ppq. The pairs are (xyz, ppq), (xyz, pqp), (xyz, qpp). Alternating the order makes 3 more pairs so we have to multiply the result by 2(see |C| below).- Only 1 pair can be made with xxx and xxx, pqr, mmn.
Now let A, B, C, D be four disjoint subset of X where,
$A$ contains only pairs of no-repeat triplets
$B$ contains only pairs of 2-repeat triplets
$C$ contains pairs of one no-repeat and one 2-repeat triplets
$D$ contains All pairs with at most one 3-repeat triplet
So, $Acup Bcup Ccup D=X$
$|A|=3^2*6$
$|B|=3^2*2$
$|C|=2*3^2*3$
$|D|=1+2*(3+3)$
So the answer is $3^2*6+3^2*2+2*3^2*3+1+2*(3+3)=139$
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
$endgroup$
add a comment |
$begingroup$
The problem can be reduced to finding the set X of ordered pair of triplets (xyz, pqr) providing $x+y+z=p+q+r=6$ and $2^x5^pleq2^y5^qleq2^z5^r$(to avoid repetition), then the size of X is the answer.
There are 7 triplets(ignoring order) that sum up to 6:
006, 015, 024, 033, 114, 123, 222
As order in the triplets matters((xyz, xyz), (xyz, xzy) etc are distinct), we can not simply find X by squaring of the set of these 7 triplets. Even squaring the set of 28 variants of the 7 triplets ($3*P(3, 3)+3*P(3,1)+1=28$) doesn't resolves to $X$. Because (xyz, xyz), (zyx, zyx) etc are distinct.
Now classifying the 7 triplets into 3 groups may help:
- no-repeat group: 123; 015; 024;
- 2-repeat group: 006; 330; 114;
- 3-repeat group: 222;
Consider the following observations
6 pairs can be made with a no-repeat triplet xyz i.e. a triplet of
the no-repeat group.
To demonstrate, (123, 123), (123, 132),
(123, 213), (123, 231), (123, 312), (123, 321) pairs can be made
with the triplet 123. As these 6 pairs represent 6 unique way to
express $10^6$($10*100*1000$, $10*500*200$, ...) the no repetition
rule($aleq bleq c$) has been followed.
6 pairs can be made with two no-repeat triplet xyz
and pqr(actually 12 pairs if we alternate the order of the pairs but we will
consider that manually in calculation).
2 pairs can be made with a 2-repeat triplet xxy.
2 pairs can be made with two 2-r triplet xxy and ppq or xyy and xpp(consider every case).
3 pairs can be made with xyz and ppq. The pairs are (xyz, ppq), (xyz, pqp), (xyz, qpp). Alternating the order makes 3 more pairs so we have to multiply the result by 2(see |C| below).- Only 1 pair can be made with xxx and xxx, pqr, mmn.
Now let A, B, C, D be four disjoint subset of X where,
$A$ contains only pairs of no-repeat triplets
$B$ contains only pairs of 2-repeat triplets
$C$ contains pairs of one no-repeat and one 2-repeat triplets
$D$ contains All pairs with at most one 3-repeat triplet
So, $Acup Bcup Ccup D=X$
$|A|=3^2*6$
$|B|=3^2*2$
$|C|=2*3^2*3$
$|D|=1+2*(3+3)$
So the answer is $3^2*6+3^2*2+2*3^2*3+1+2*(3+3)=139$
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
$endgroup$
The problem can be reduced to finding the set X of ordered pair of triplets (xyz, pqr) providing $x+y+z=p+q+r=6$ and $2^x5^pleq2^y5^qleq2^z5^r$(to avoid repetition), then the size of X is the answer.
There are 7 triplets(ignoring order) that sum up to 6:
006, 015, 024, 033, 114, 123, 222
As order in the triplets matters((xyz, xyz), (xyz, xzy) etc are distinct), we can not simply find X by squaring of the set of these 7 triplets. Even squaring the set of 28 variants of the 7 triplets ($3*P(3, 3)+3*P(3,1)+1=28$) doesn't resolves to $X$. Because (xyz, xyz), (zyx, zyx) etc are distinct.
Now classifying the 7 triplets into 3 groups may help:
- no-repeat group: 123; 015; 024;
- 2-repeat group: 006; 330; 114;
- 3-repeat group: 222;
Consider the following observations
6 pairs can be made with a no-repeat triplet xyz i.e. a triplet of
the no-repeat group.
To demonstrate, (123, 123), (123, 132),
(123, 213), (123, 231), (123, 312), (123, 321) pairs can be made
with the triplet 123. As these 6 pairs represent 6 unique way to
express $10^6$($10*100*1000$, $10*500*200$, ...) the no repetition
rule($aleq bleq c$) has been followed.
6 pairs can be made with two no-repeat triplet xyz
and pqr(actually 12 pairs if we alternate the order of the pairs but we will
consider that manually in calculation).
2 pairs can be made with a 2-repeat triplet xxy.
2 pairs can be made with two 2-r triplet xxy and ppq or xyy and xpp(consider every case).
3 pairs can be made with xyz and ppq. The pairs are (xyz, ppq), (xyz, pqp), (xyz, qpp). Alternating the order makes 3 more pairs so we have to multiply the result by 2(see |C| below).- Only 1 pair can be made with xxx and xxx, pqr, mmn.
Now let A, B, C, D be four disjoint subset of X where,
$A$ contains only pairs of no-repeat triplets
$B$ contains only pairs of 2-repeat triplets
$C$ contains pairs of one no-repeat and one 2-repeat triplets
$D$ contains All pairs with at most one 3-repeat triplet
So, $Acup Bcup Ccup D=X$
$|A|=3^2*6$
$|B|=3^2*2$
$|C|=2*3^2*3$
$|D|=1+2*(3+3)$
So the answer is $3^2*6+3^2*2+2*3^2*3+1+2*(3+3)=139$
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
answered Jan 10 at 10:23
Mahmud Nabil SnigdhoMahmud Nabil Snigdho
12
12
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f273137%2fhow-many-ways-to-write-one-million-as-a-product-of-three-positive-integers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
I think some working or demonstration of effort should be given. As a very general comment, this kind of problem calls for some careful organisation of cases - so some clarity of thought. It is worth trying this out for yourself before asking for help, because it always looks so blindingly obvious when you are told a good way of doing it - and that doesn't do anything much to help you solve the next problem.
$endgroup$
– Mark Bennet
Jan 8 '13 at 23:17
$begingroup$
Sorry didn't have time to write my working out beforehand, just came back to write my working out now.
$endgroup$
– DeeDee
Jan 8 '13 at 23:35