How many maximum triangles can be made?
There are $8$ points on a plane no three are colinear how many maximum triangles can be made s.t no two triangles have more than one point in common.
Now I can choose $3$ points from $8$ points in $^8C_3$ ways and two triangles can have two points in common if I choose $5$ points make $2$ triangles out of it and that can be made in $^8C_6 times ^6C_3 times frac 12$ ways. So the answer should be $^8C_3-(^8C_5 times ^5C_3times frac 12)$.
Am I double counting anything?
After seeing one comment and thinking a bit I feel that method of complementation will be harder here and I am thinking about how many ways to draw a triangle instead of maximum how many triangles,
So another approach: I can choose three points from $8$ points and draw the 1st triangle then the second triangle can be drawn taking one point from the first(because we are maximizing) and $2$ others from the remaining $5$ points. So we have used $5$ points and drew $2$ triangles. Then we can draw atmost one more triangle. So $3$ is the answer.
combinatorics discrete-mathematics proof-verification graph-theory contest-math
add a comment |
There are $8$ points on a plane no three are colinear how many maximum triangles can be made s.t no two triangles have more than one point in common.
Now I can choose $3$ points from $8$ points in $^8C_3$ ways and two triangles can have two points in common if I choose $5$ points make $2$ triangles out of it and that can be made in $^8C_6 times ^6C_3 times frac 12$ ways. So the answer should be $^8C_3-(^8C_5 times ^5C_3times frac 12)$.
Am I double counting anything?
After seeing one comment and thinking a bit I feel that method of complementation will be harder here and I am thinking about how many ways to draw a triangle instead of maximum how many triangles,
So another approach: I can choose three points from $8$ points and draw the 1st triangle then the second triangle can be drawn taking one point from the first(because we are maximizing) and $2$ others from the remaining $5$ points. So we have used $5$ points and drew $2$ triangles. Then we can draw atmost one more triangle. So $3$ is the answer.
combinatorics discrete-mathematics proof-verification graph-theory contest-math
1
Seeing as your answer is a negative number, probably not.
– bof
1 hour ago
I am double counting something then...
– Gimgim
1 hour ago
Ah - what's the question? How many ways to do it (whatever it is)? The maximum number of triangles we can fit in under these rules? If its' the latter, the answer is certainly more than three - it only takes six points for four triangles, based on alternating faces of an octahedron.
– jmerry
1 hour ago
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
– bof
55 mins ago
add a comment |
There are $8$ points on a plane no three are colinear how many maximum triangles can be made s.t no two triangles have more than one point in common.
Now I can choose $3$ points from $8$ points in $^8C_3$ ways and two triangles can have two points in common if I choose $5$ points make $2$ triangles out of it and that can be made in $^8C_6 times ^6C_3 times frac 12$ ways. So the answer should be $^8C_3-(^8C_5 times ^5C_3times frac 12)$.
Am I double counting anything?
After seeing one comment and thinking a bit I feel that method of complementation will be harder here and I am thinking about how many ways to draw a triangle instead of maximum how many triangles,
So another approach: I can choose three points from $8$ points and draw the 1st triangle then the second triangle can be drawn taking one point from the first(because we are maximizing) and $2$ others from the remaining $5$ points. So we have used $5$ points and drew $2$ triangles. Then we can draw atmost one more triangle. So $3$ is the answer.
combinatorics discrete-mathematics proof-verification graph-theory contest-math
There are $8$ points on a plane no three are colinear how many maximum triangles can be made s.t no two triangles have more than one point in common.
Now I can choose $3$ points from $8$ points in $^8C_3$ ways and two triangles can have two points in common if I choose $5$ points make $2$ triangles out of it and that can be made in $^8C_6 times ^6C_3 times frac 12$ ways. So the answer should be $^8C_3-(^8C_5 times ^5C_3times frac 12)$.
Am I double counting anything?
After seeing one comment and thinking a bit I feel that method of complementation will be harder here and I am thinking about how many ways to draw a triangle instead of maximum how many triangles,
So another approach: I can choose three points from $8$ points and draw the 1st triangle then the second triangle can be drawn taking one point from the first(because we are maximizing) and $2$ others from the remaining $5$ points. So we have used $5$ points and drew $2$ triangles. Then we can draw atmost one more triangle. So $3$ is the answer.
combinatorics discrete-mathematics proof-verification graph-theory contest-math
combinatorics discrete-mathematics proof-verification graph-theory contest-math
edited 41 mins ago
asked 1 hour ago
Gimgim
1438
1438
1
Seeing as your answer is a negative number, probably not.
– bof
1 hour ago
I am double counting something then...
– Gimgim
1 hour ago
Ah - what's the question? How many ways to do it (whatever it is)? The maximum number of triangles we can fit in under these rules? If its' the latter, the answer is certainly more than three - it only takes six points for four triangles, based on alternating faces of an octahedron.
– jmerry
1 hour ago
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
– bof
55 mins ago
add a comment |
1
Seeing as your answer is a negative number, probably not.
– bof
1 hour ago
I am double counting something then...
– Gimgim
1 hour ago
Ah - what's the question? How many ways to do it (whatever it is)? The maximum number of triangles we can fit in under these rules? If its' the latter, the answer is certainly more than three - it only takes six points for four triangles, based on alternating faces of an octahedron.
– jmerry
1 hour ago
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
– bof
55 mins ago
1
1
Seeing as your answer is a negative number, probably not.
– bof
1 hour ago
Seeing as your answer is a negative number, probably not.
– bof
1 hour ago
I am double counting something then...
– Gimgim
1 hour ago
I am double counting something then...
– Gimgim
1 hour ago
Ah - what's the question? How many ways to do it (whatever it is)? The maximum number of triangles we can fit in under these rules? If its' the latter, the answer is certainly more than three - it only takes six points for four triangles, based on alternating faces of an octahedron.
– jmerry
1 hour ago
Ah - what's the question? How many ways to do it (whatever it is)? The maximum number of triangles we can fit in under these rules? If its' the latter, the answer is certainly more than three - it only takes six points for four triangles, based on alternating faces of an octahedron.
– jmerry
1 hour ago
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
– bof
55 mins ago
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
– bof
55 mins ago
add a comment |
2 Answers
2
active
oldest
votes
I have only a partial answer to your question: the maximum number of triangles is either $8$ or $9$.
You can't have more than $9$ triangles, because there are only $^8C_2=28$ edges determined by the $8$ points, each triangle needs $3$ edges, and no edge may be used by more than one triangle. So the number of triangles is at most $lfloor28/3rfloor=9$.
I don't see how to construct a set of $9$ triangles satisfying your conditions, but I can get $8$. Namely, if we label the points $A,B,C,D,E,F,G,H$, the following $8$ triangles work:
$$ABC, ADG, AFH, BEH, BFG, CDH, CEG, DEH$$
P.S. In fact, $8$ is the maximum. Let $p$ be the number of points (so $p=9$), let $t$ be the number of triangles, and let $n$ be the number of pairs $(P,T)$ where $T$ is a triangle and $P$ is a vertex of $T$. Then $n=3t$ (since each triangle has $3$ vertices), and $nle3p$ (since at most $3$ triangles can contain a given point, so $tle p=8$.
P.P.S. In case you're wondering how I found that set of $8$ triangles, I started with the well-known example of $12$ triangles on $9$ points (Steiner triple system) and deleted one point. Namely, I wrote the letters A to I in a $3times3$ square array, took the $6$ rows and columns and the $6$ "diagonals", and then deleted the ones containing the letter I.
Ohhh! yes!! I didn't think in that way
– Gimgim
49 mins ago
@Gimgim I added some more explanation to myu answer.
– bof
33 mins ago
add a comment |
bof gives a great justification of why it is eight or nine with an example of $8$.
Here is why it can't be nine. If there were nine triangles, they would use $27$ points, so one point would have to be used at least $4$ times. Each of these four triangles creates two edges containing this point, so we have at least $8$ edges containing this point. But there are only $7$ other points there must be a duplicate edge.
New contributor
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
39 mins ago
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%2f3061329%2fhow-many-maximum-triangles-can-be-made%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
I have only a partial answer to your question: the maximum number of triangles is either $8$ or $9$.
You can't have more than $9$ triangles, because there are only $^8C_2=28$ edges determined by the $8$ points, each triangle needs $3$ edges, and no edge may be used by more than one triangle. So the number of triangles is at most $lfloor28/3rfloor=9$.
I don't see how to construct a set of $9$ triangles satisfying your conditions, but I can get $8$. Namely, if we label the points $A,B,C,D,E,F,G,H$, the following $8$ triangles work:
$$ABC, ADG, AFH, BEH, BFG, CDH, CEG, DEH$$
P.S. In fact, $8$ is the maximum. Let $p$ be the number of points (so $p=9$), let $t$ be the number of triangles, and let $n$ be the number of pairs $(P,T)$ where $T$ is a triangle and $P$ is a vertex of $T$. Then $n=3t$ (since each triangle has $3$ vertices), and $nle3p$ (since at most $3$ triangles can contain a given point, so $tle p=8$.
P.P.S. In case you're wondering how I found that set of $8$ triangles, I started with the well-known example of $12$ triangles on $9$ points (Steiner triple system) and deleted one point. Namely, I wrote the letters A to I in a $3times3$ square array, took the $6$ rows and columns and the $6$ "diagonals", and then deleted the ones containing the letter I.
Ohhh! yes!! I didn't think in that way
– Gimgim
49 mins ago
@Gimgim I added some more explanation to myu answer.
– bof
33 mins ago
add a comment |
I have only a partial answer to your question: the maximum number of triangles is either $8$ or $9$.
You can't have more than $9$ triangles, because there are only $^8C_2=28$ edges determined by the $8$ points, each triangle needs $3$ edges, and no edge may be used by more than one triangle. So the number of triangles is at most $lfloor28/3rfloor=9$.
I don't see how to construct a set of $9$ triangles satisfying your conditions, but I can get $8$. Namely, if we label the points $A,B,C,D,E,F,G,H$, the following $8$ triangles work:
$$ABC, ADG, AFH, BEH, BFG, CDH, CEG, DEH$$
P.S. In fact, $8$ is the maximum. Let $p$ be the number of points (so $p=9$), let $t$ be the number of triangles, and let $n$ be the number of pairs $(P,T)$ where $T$ is a triangle and $P$ is a vertex of $T$. Then $n=3t$ (since each triangle has $3$ vertices), and $nle3p$ (since at most $3$ triangles can contain a given point, so $tle p=8$.
P.P.S. In case you're wondering how I found that set of $8$ triangles, I started with the well-known example of $12$ triangles on $9$ points (Steiner triple system) and deleted one point. Namely, I wrote the letters A to I in a $3times3$ square array, took the $6$ rows and columns and the $6$ "diagonals", and then deleted the ones containing the letter I.
Ohhh! yes!! I didn't think in that way
– Gimgim
49 mins ago
@Gimgim I added some more explanation to myu answer.
– bof
33 mins ago
add a comment |
I have only a partial answer to your question: the maximum number of triangles is either $8$ or $9$.
You can't have more than $9$ triangles, because there are only $^8C_2=28$ edges determined by the $8$ points, each triangle needs $3$ edges, and no edge may be used by more than one triangle. So the number of triangles is at most $lfloor28/3rfloor=9$.
I don't see how to construct a set of $9$ triangles satisfying your conditions, but I can get $8$. Namely, if we label the points $A,B,C,D,E,F,G,H$, the following $8$ triangles work:
$$ABC, ADG, AFH, BEH, BFG, CDH, CEG, DEH$$
P.S. In fact, $8$ is the maximum. Let $p$ be the number of points (so $p=9$), let $t$ be the number of triangles, and let $n$ be the number of pairs $(P,T)$ where $T$ is a triangle and $P$ is a vertex of $T$. Then $n=3t$ (since each triangle has $3$ vertices), and $nle3p$ (since at most $3$ triangles can contain a given point, so $tle p=8$.
P.P.S. In case you're wondering how I found that set of $8$ triangles, I started with the well-known example of $12$ triangles on $9$ points (Steiner triple system) and deleted one point. Namely, I wrote the letters A to I in a $3times3$ square array, took the $6$ rows and columns and the $6$ "diagonals", and then deleted the ones containing the letter I.
I have only a partial answer to your question: the maximum number of triangles is either $8$ or $9$.
You can't have more than $9$ triangles, because there are only $^8C_2=28$ edges determined by the $8$ points, each triangle needs $3$ edges, and no edge may be used by more than one triangle. So the number of triangles is at most $lfloor28/3rfloor=9$.
I don't see how to construct a set of $9$ triangles satisfying your conditions, but I can get $8$. Namely, if we label the points $A,B,C,D,E,F,G,H$, the following $8$ triangles work:
$$ABC, ADG, AFH, BEH, BFG, CDH, CEG, DEH$$
P.S. In fact, $8$ is the maximum. Let $p$ be the number of points (so $p=9$), let $t$ be the number of triangles, and let $n$ be the number of pairs $(P,T)$ where $T$ is a triangle and $P$ is a vertex of $T$. Then $n=3t$ (since each triangle has $3$ vertices), and $nle3p$ (since at most $3$ triangles can contain a given point, so $tle p=8$.
P.P.S. In case you're wondering how I found that set of $8$ triangles, I started with the well-known example of $12$ triangles on $9$ points (Steiner triple system) and deleted one point. Namely, I wrote the letters A to I in a $3times3$ square array, took the $6$ rows and columns and the $6$ "diagonals", and then deleted the ones containing the letter I.
edited 33 mins ago
answered 58 mins ago
bof
50.4k457119
50.4k457119
Ohhh! yes!! I didn't think in that way
– Gimgim
49 mins ago
@Gimgim I added some more explanation to myu answer.
– bof
33 mins ago
add a comment |
Ohhh! yes!! I didn't think in that way
– Gimgim
49 mins ago
@Gimgim I added some more explanation to myu answer.
– bof
33 mins ago
Ohhh! yes!! I didn't think in that way
– Gimgim
49 mins ago
Ohhh! yes!! I didn't think in that way
– Gimgim
49 mins ago
@Gimgim I added some more explanation to myu answer.
– bof
33 mins ago
@Gimgim I added some more explanation to myu answer.
– bof
33 mins ago
add a comment |
bof gives a great justification of why it is eight or nine with an example of $8$.
Here is why it can't be nine. If there were nine triangles, they would use $27$ points, so one point would have to be used at least $4$ times. Each of these four triangles creates two edges containing this point, so we have at least $8$ edges containing this point. But there are only $7$ other points there must be a duplicate edge.
New contributor
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
39 mins ago
add a comment |
bof gives a great justification of why it is eight or nine with an example of $8$.
Here is why it can't be nine. If there were nine triangles, they would use $27$ points, so one point would have to be used at least $4$ times. Each of these four triangles creates two edges containing this point, so we have at least $8$ edges containing this point. But there are only $7$ other points there must be a duplicate edge.
New contributor
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
39 mins ago
add a comment |
bof gives a great justification of why it is eight or nine with an example of $8$.
Here is why it can't be nine. If there were nine triangles, they would use $27$ points, so one point would have to be used at least $4$ times. Each of these four triangles creates two edges containing this point, so we have at least $8$ edges containing this point. But there are only $7$ other points there must be a duplicate edge.
New contributor
bof gives a great justification of why it is eight or nine with an example of $8$.
Here is why it can't be nine. If there were nine triangles, they would use $27$ points, so one point would have to be used at least $4$ times. Each of these four triangles creates two edges containing this point, so we have at least $8$ edges containing this point. But there are only $7$ other points there must be a duplicate edge.
New contributor
edited 37 mins ago
Gimgim
1438
1438
New contributor
answered 43 mins ago
Erik Parkinson
4626
4626
New contributor
New contributor
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
39 mins ago
add a comment |
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
39 mins ago
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
39 mins ago
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
39 mins ago
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3061329%2fhow-many-maximum-triangles-can-be-made%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
1
Seeing as your answer is a negative number, probably not.
– bof
1 hour ago
I am double counting something then...
– Gimgim
1 hour ago
Ah - what's the question? How many ways to do it (whatever it is)? The maximum number of triangles we can fit in under these rules? If its' the latter, the answer is certainly more than three - it only takes six points for four triangles, based on alternating faces of an octahedron.
– jmerry
1 hour ago
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
– bof
55 mins ago