How many maximum triangles can be made?












3














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
    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
    41 mins ago










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
















3














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
    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
    41 mins ago










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














3












3








3







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 18 mins ago

























asked 1 hour ago









Gimgim

1388




1388








  • 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
    41 mins ago










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














  • 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
    41 mins ago










  • @jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
    – bof
    32 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
41 mins 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
41 mins ago












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




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










2 Answers
2






active

oldest

votes


















3














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
    27 mins ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    10 mins 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
    17 mins 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









3














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
    27 mins ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    10 mins ago
















3














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
    27 mins ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    10 mins ago














3












3








3






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 10 mins ago

























answered 35 mins ago









bof

50.4k457119




50.4k457119












  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    27 mins ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    10 mins ago


















  • Ohhh! yes!! I didn't think in that way
    – Gimgim
    27 mins ago










  • @Gimgim I added some more explanation to myu answer.
    – bof
    10 mins ago
















Ohhh! yes!! I didn't think in that way
– Gimgim
27 mins ago




Ohhh! yes!! I didn't think in that way
– Gimgim
27 mins ago












@Gimgim I added some more explanation to myu answer.
– bof
10 mins ago




@Gimgim I added some more explanation to myu answer.
– bof
10 mins 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
    17 mins 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
    17 mins 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 15 mins ago









Gimgim

1388




1388






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 21 mins ago









Erik Parkinson

4626




4626




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
    17 mins ago


















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
















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




Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
– bof
17 mins 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

404 Error Contact Form 7 ajax form submitting

How to know if a Active Directory user can login interactively

Refactoring coordinates for Minecraft Pi buildings written in Python