How many Distinct triangle can be made from stick of length N?
$begingroup$
You are given a stick of length N. You want to break it in three pieces such that it can form a triangle. How many distinct triangles can you make? Two triangles are equal if all the side lengths are same when sorted in ascending order of length. So (1, 3, 2) is same to (3, 1, 2) because their side lengths are same if we sort them, which is (1, 2, 3). But (1, 3, 4) is not same with (1, 2, 3). Suppose the lengths of three pieces are X, Y, Z (X ≤ Y ≤ Z) respectively. Following constraints should be maintained:
X, Y, Z > 0.
X, Y, Z is an integer.
X + Y >= Z
X + Y + Z = N
For example if N = 14, then there are 7 triangles: (1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6), (4, 4, 6), (4, 5, 5).
combinatorics geometry
edited Nov 21 '17 at 14:31
CiaPan
10k11246
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
$endgroup$
|
show 1 more comment
$begingroup$
You are given a stick of length N. You want to break it in three pieces such that it can form a triangle. How many distinct triangles can you make? Two triangles are equal if all the side lengths are same when sorted in ascending order of length. So (1, 3, 2) is same to (3, 1, 2) because their side lengths are same if we sort them, which is (1, 2, 3). But (1, 3, 4) is not same with (1, 2, 3). Suppose the lengths of three pieces are X, Y, Z (X ≤ Y ≤ Z) respectively. Following constraints should be maintained:
X, Y, Z > 0.
X, Y, Z is an integer.
X + Y >= Z
X + Y + Z = N
For example if N = 14, then there are 7 triangles: (1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6), (4, 4, 6), (4, 5, 5).
combinatorics geometry
edited Nov 21 '17 at 14:31
CiaPan
10k11246
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
$endgroup$
$begingroup$
It might help to know that the triangle inequality test can be simplified here to check the sum of two smaller parts exceeds the larger part.
$endgroup$
– hardmath
Jan 3 '16 at 13:37
2
$begingroup$
Hint: The longest side cannot be bigger than $N/2$, and cannot be smaller than $N/3$.
$endgroup$
– Frentos
Jan 3 '16 at 13:37
1
$begingroup$
(1,6,7),(2,5,7), and (3,4,7) will not make triangles.The sum of any two sides must be strictly greater than the third side.
$endgroup$
– DanielWainfleet
Jan 3 '16 at 13:43
$begingroup$
@user254665 , look at the constrains , X + Y >= Z , where on earth you found strictly greater ?
$endgroup$
– Code Mechanic
Jan 3 '16 at 13:44
1
$begingroup$
oeis.org/A005044 gives the sequence for the number of non-degenerate triangles (i.e., not counting those with $X+Y=Z$).
$endgroup$
– Barry Cipra
Jan 3 '16 at 13:56
|
show 1 more comment
$begingroup$
You are given a stick of length N. You want to break it in three pieces such that it can form a triangle. How many distinct triangles can you make? Two triangles are equal if all the side lengths are same when sorted in ascending order of length. So (1, 3, 2) is same to (3, 1, 2) because their side lengths are same if we sort them, which is (1, 2, 3). But (1, 3, 4) is not same with (1, 2, 3). Suppose the lengths of three pieces are X, Y, Z (X ≤ Y ≤ Z) respectively. Following constraints should be maintained:
X, Y, Z > 0.
X, Y, Z is an integer.
X + Y >= Z
X + Y + Z = N
For example if N = 14, then there are 7 triangles: (1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6), (4, 4, 6), (4, 5, 5).
combinatorics geometry
edited Nov 21 '17 at 14:31
CiaPan
10k11246
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
$endgroup$
You are given a stick of length N. You want to break it in three pieces such that it can form a triangle. How many distinct triangles can you make? Two triangles are equal if all the side lengths are same when sorted in ascending order of length. So (1, 3, 2) is same to (3, 1, 2) because their side lengths are same if we sort them, which is (1, 2, 3). But (1, 3, 4) is not same with (1, 2, 3). Suppose the lengths of three pieces are X, Y, Z (X ≤ Y ≤ Z) respectively. Following constraints should be maintained:
X, Y, Z > 0.
X, Y, Z is an integer.
X + Y >= Z
X + Y + Z = N
For example if N = 14, then there are 7 triangles: (1, 6, 7), (2, 5, 7), (2, 6, 6), (3, 4, 7), (3, 5, 6), (4, 4, 6), (4, 5, 5).
combinatorics geometry
combinatorics geometry
edited Nov 21 '17 at 14:31
CiaPan
10k11246
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
edited Nov 21 '17 at 14:31
CiaPan
10k11246
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
edited Nov 21 '17 at 14:31
CiaPan
10k11246
edited Nov 21 '17 at 14:31
CiaPan
10k11246
edited Nov 21 '17 at 14:31
CiaPan
10k11246
10k11246
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
asked Jan 3 '16 at 13:31
Code MechanicCode Mechanic
135
135
$begingroup$
It might help to know that the triangle inequality test can be simplified here to check the sum of two smaller parts exceeds the larger part.
$endgroup$
– hardmath
Jan 3 '16 at 13:37
2
$begingroup$
Hint: The longest side cannot be bigger than $N/2$, and cannot be smaller than $N/3$.
$endgroup$
– Frentos
Jan 3 '16 at 13:37
1
$begingroup$
(1,6,7),(2,5,7), and (3,4,7) will not make triangles.The sum of any two sides must be strictly greater than the third side.
$endgroup$
– DanielWainfleet
Jan 3 '16 at 13:43
$begingroup$
@user254665 , look at the constrains , X + Y >= Z , where on earth you found strictly greater ?
$endgroup$
– Code Mechanic
Jan 3 '16 at 13:44
1
$begingroup$
oeis.org/A005044 gives the sequence for the number of non-degenerate triangles (i.e., not counting those with $X+Y=Z$).
$endgroup$
– Barry Cipra
Jan 3 '16 at 13:56
|
show 1 more comment
$begingroup$
It might help to know that the triangle inequality test can be simplified here to check the sum of two smaller parts exceeds the larger part.
$endgroup$
– hardmath
Jan 3 '16 at 13:37
2
$begingroup$
Hint: The longest side cannot be bigger than $N/2$, and cannot be smaller than $N/3$.
$endgroup$
– Frentos
Jan 3 '16 at 13:37
1
$begingroup$
(1,6,7),(2,5,7), and (3,4,7) will not make triangles.The sum of any two sides must be strictly greater than the third side.
$endgroup$
– DanielWainfleet
Jan 3 '16 at 13:43
$begingroup$
@user254665 , look at the constrains , X + Y >= Z , where on earth you found strictly greater ?
$endgroup$
– Code Mechanic
Jan 3 '16 at 13:44
1
$begingroup$
oeis.org/A005044 gives the sequence for the number of non-degenerate triangles (i.e., not counting those with $X+Y=Z$).
$endgroup$
– Barry Cipra
Jan 3 '16 at 13:56
$begingroup$
It might help to know that the triangle inequality test can be simplified here to check the sum of two smaller parts exceeds the larger part.
$endgroup$
– hardmath
Jan 3 '16 at 13:37
$begingroup$
It might help to know that the triangle inequality test can be simplified here to check the sum of two smaller parts exceeds the larger part.
$endgroup$
– hardmath
Jan 3 '16 at 13:37
2
2
$begingroup$
Hint: The longest side cannot be bigger than $N/2$, and cannot be smaller than $N/3$.
$endgroup$
– Frentos
Jan 3 '16 at 13:37
$begingroup$
Hint: The longest side cannot be bigger than $N/2$, and cannot be smaller than $N/3$.
$endgroup$
– Frentos
Jan 3 '16 at 13:37
1
1
$begingroup$
(1,6,7),(2,5,7), and (3,4,7) will not make triangles.The sum of any two sides must be strictly greater than the third side.
$endgroup$
– DanielWainfleet
Jan 3 '16 at 13:43
$begingroup$
(1,6,7),(2,5,7), and (3,4,7) will not make triangles.The sum of any two sides must be strictly greater than the third side.
$endgroup$
– DanielWainfleet
Jan 3 '16 at 13:43
$begingroup$
@user254665 , look at the constrains , X + Y >= Z , where on earth you found strictly greater ?
$endgroup$
– Code Mechanic
Jan 3 '16 at 13:44
$begingroup$
@user254665 , look at the constrains , X + Y >= Z , where on earth you found strictly greater ?
$endgroup$
– Code Mechanic
Jan 3 '16 at 13:44
1
1
$begingroup$
oeis.org/A005044 gives the sequence for the number of non-degenerate triangles (i.e., not counting those with $X+Y=Z$).
$endgroup$
– Barry Cipra
Jan 3 '16 at 13:56
$begingroup$
oeis.org/A005044 gives the sequence for the number of non-degenerate triangles (i.e., not counting those with $X+Y=Z$).
$endgroup$
– Barry Cipra
Jan 3 '16 at 13:56
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
As noted by Barry Cipra, the number of nondegenerate triangles is given in OEIS A005044. Allowing degenerate ones (due to the restriction $X+Y ge Z$ permitting equality) adds $lfloor frac n4 rfloor$ when $n$ is even and makes no change when $n$ is odd. This is because to have $X+Y=Z$ with $X le Y le Z$ we must have $Z$ even, then we count the values for $X$ as from $1$ to $lfloor frac Z2 rfloor$ I didn't find the resulting sequence in OEIS.
edited Apr 10 '17 at 23:28
Deepak
17k11536
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
$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%2f1598306%2fhow-many-distinct-triangle-can-be-made-from-stick-of-length-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As noted by Barry Cipra, the number of nondegenerate triangles is given in OEIS A005044. Allowing degenerate ones (due to the restriction $X+Y ge Z$ permitting equality) adds $lfloor frac n4 rfloor$ when $n$ is even and makes no change when $n$ is odd. This is because to have $X+Y=Z$ with $X le Y le Z$ we must have $Z$ even, then we count the values for $X$ as from $1$ to $lfloor frac Z2 rfloor$ I didn't find the resulting sequence in OEIS.
edited Apr 10 '17 at 23:28
Deepak
17k11536
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
As noted by Barry Cipra, the number of nondegenerate triangles is given in OEIS A005044. Allowing degenerate ones (due to the restriction $X+Y ge Z$ permitting equality) adds $lfloor frac n4 rfloor$ when $n$ is even and makes no change when $n$ is odd. This is because to have $X+Y=Z$ with $X le Y le Z$ we must have $Z$ even, then we count the values for $X$ as from $1$ to $lfloor frac Z2 rfloor$ I didn't find the resulting sequence in OEIS.
edited Apr 10 '17 at 23:28
Deepak
17k11536
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
$endgroup$
add a comment |
$begingroup$
As noted by Barry Cipra, the number of nondegenerate triangles is given in OEIS A005044. Allowing degenerate ones (due to the restriction $X+Y ge Z$ permitting equality) adds $lfloor frac n4 rfloor$ when $n$ is even and makes no change when $n$ is odd. This is because to have $X+Y=Z$ with $X le Y le Z$ we must have $Z$ even, then we count the values for $X$ as from $1$ to $lfloor frac Z2 rfloor$ I didn't find the resulting sequence in OEIS.
edited Apr 10 '17 at 23:28
Deepak
17k11536
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
$endgroup$
As noted by Barry Cipra, the number of nondegenerate triangles is given in OEIS A005044. Allowing degenerate ones (due to the restriction $X+Y ge Z$ permitting equality) adds $lfloor frac n4 rfloor$ when $n$ is even and makes no change when $n$ is odd. This is because to have $X+Y=Z$ with $X le Y le Z$ we must have $Z$ even, then we count the values for $X$ as from $1$ to $lfloor frac Z2 rfloor$ I didn't find the resulting sequence in OEIS.
edited Apr 10 '17 at 23:28
Deepak
17k11536
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
edited Apr 10 '17 at 23:28
Deepak
17k11536
edited Apr 10 '17 at 23:28
Deepak
17k11536
edited Apr 10 '17 at 23:28
Deepak
17k11536
17k11536
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
answered Jan 3 '16 at 14:23
Ross MillikanRoss Millikan
297k23198371
297k23198371
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%2f1598306%2fhow-many-distinct-triangle-can-be-made-from-stick-of-length-n%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
$begingroup$
It might help to know that the triangle inequality test can be simplified here to check the sum of two smaller parts exceeds the larger part.
$endgroup$
– hardmath
Jan 3 '16 at 13:37
2
$begingroup$
Hint: The longest side cannot be bigger than $N/2$, and cannot be smaller than $N/3$.
$endgroup$
– Frentos
Jan 3 '16 at 13:37
1
$begingroup$
(1,6,7),(2,5,7), and (3,4,7) will not make triangles.The sum of any two sides must be strictly greater than the third side.
$endgroup$
– DanielWainfleet
Jan 3 '16 at 13:43
$begingroup$
@user254665 , look at the constrains , X + Y >= Z , where on earth you found strictly greater ?
$endgroup$
– Code Mechanic
Jan 3 '16 at 13:44
1
$begingroup$
oeis.org/A005044 gives the sequence for the number of non-degenerate triangles (i.e., not counting those with $X+Y=Z$).
$endgroup$
– Barry Cipra
Jan 3 '16 at 13:56