How many maximum triangles can be made?












4














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.










share|cite|improve this question




















  • 1




    Seeing as your answer is a negative number, probably not.
    – bof
    2 hours ago










  • I am double counting something then...
    – Gimgim
    2 hours 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
    1 hour ago
















4














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.










share|cite|improve this question




















  • 1




    Seeing as your answer is a negative number, probably not.
    – bof
    2 hours ago










  • I am double counting something then...
    – Gimgim
    2 hours 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
    1 hour ago














4












4








4







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.










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 1 hour ago

























asked 2 hours ago









Gimgim

1458




1458








  • 1




    Seeing as your answer is a negative number, probably not.
    – bof
    2 hours ago










  • I am double counting something then...
    – Gimgim
    2 hours 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
    1 hour ago














  • 1




    Seeing as your answer is a negative number, probably not.
    – bof
    2 hours ago










  • I am double counting something then...
    – Gimgim
    2 hours 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
    1 hour ago








1




1




Seeing as your answer is a negative number, probably not.
– bof
2 hours ago




Seeing as your answer is a negative number, probably not.
– bof
2 hours ago












I am double counting something then...
– Gimgim
2 hours ago




I am double counting something then...
– Gimgim
2 hours 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
1 hour ago




@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
– bof
1 hour ago










2 Answers
2






active

oldest

votes


















4














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.






share|cite|improve this answer























  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    1 hour ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    1 hour ago



















2














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.






share|cite|improve this answer










New contributor




Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















  • Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
    – bof
    1 hour ago











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
});


}
});














draft saved

draft discarded


















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









4














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.






share|cite|improve this answer























  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    1 hour ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    1 hour ago
















4














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.






share|cite|improve this answer























  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    1 hour ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    1 hour ago














4












4








4






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.






share|cite|improve this answer














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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 31 mins ago

























answered 1 hour ago









bof

50.4k457119




50.4k457119












  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    1 hour ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    1 hour ago


















  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    1 hour ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    1 hour ago
















Ohhh! yes!! I didn't think in that way
– Gimgim
1 hour ago




Ohhh! yes!! I didn't think in that way
– Gimgim
1 hour ago












@Gimgim I added some more explanation to myu answer.
– bof
1 hour ago




@Gimgim I added some more explanation to myu answer.
– bof
1 hour ago











2














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.






share|cite|improve this answer










New contributor




Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















  • Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
    – bof
    1 hour ago
















2














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.






share|cite|improve this answer










New contributor




Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















  • Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
    – bof
    1 hour ago














2












2








2






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.






share|cite|improve this answer










New contributor




Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









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.







share|cite|improve this answer










New contributor




Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this answer



share|cite|improve this answer








edited 1 hour ago









Gimgim

1458




1458






New contributor




Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









answered 1 hour ago









Erik Parkinson

5076




5076




New contributor




Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Erik Parkinson is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
    – bof
    1 hour ago


















  • Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
    – bof
    1 hour ago
















Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
1 hour ago




Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
1 hour ago


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Contact image not getting when fetch all contact list from iPhone by CNContact

count number of partitions of a set with n elements into k subsets

A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks