How many maximum triangles can be made?












7














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
    yesterday










  • I am double counting something then...
    – Gimgim
    yesterday










  • 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
    yesterday










  • @jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
    – bof
    yesterday










  • What does "can be made" mean?
    – DanielV
    yesterday
















7














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
    yesterday










  • I am double counting something then...
    – Gimgim
    yesterday










  • 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
    yesterday










  • @jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
    – bof
    yesterday










  • What does "can be made" mean?
    – DanielV
    yesterday














7












7








7







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 yesterday

























asked yesterday









Gimgim

1609




1609








  • 1




    Seeing as your answer is a negative number, probably not.
    – bof
    yesterday










  • I am double counting something then...
    – Gimgim
    yesterday










  • 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
    yesterday










  • @jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
    – bof
    yesterday










  • What does "can be made" mean?
    – DanielV
    yesterday














  • 1




    Seeing as your answer is a negative number, probably not.
    – bof
    yesterday










  • I am double counting something then...
    – Gimgim
    yesterday










  • 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
    yesterday










  • @jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
    – bof
    yesterday










  • What does "can be made" mean?
    – DanielV
    yesterday








1




1




Seeing as your answer is a negative number, probably not.
– bof
yesterday




Seeing as your answer is a negative number, probably not.
– bof
yesterday












I am double counting something then...
– Gimgim
yesterday




I am double counting something then...
– Gimgim
yesterday












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
yesterday




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
yesterday












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




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












What does "can be made" mean?
– DanielV
yesterday




What does "can be made" mean?
– DanielV
yesterday










2 Answers
2






active

oldest

votes


















7














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=8$), 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
    yesterday



















6














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
    yesterday











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









7














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=8$), 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
    yesterday
















7














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=8$), 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
    yesterday














7












7








7






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=8$), 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=8$), 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 yesterday

























answered yesterday









bof

50.4k457119




50.4k457119












  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    yesterday


















  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    yesterday
















Ohhh! yes!! I didn't think in that way
– Gimgim
yesterday




Ohhh! yes!! I didn't think in that way
– Gimgim
yesterday











6














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
    yesterday
















6














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
    yesterday














6












6








6






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 yesterday









Gimgim

1609




1609






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 yesterday









Erik Parkinson

9069




9069




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
    yesterday


















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
















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




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


















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

1300-talet

1300-talet

Display a custom attribute below product name in the front-end Magento 1.9.3.8