How many maximum triangles can be made?
Clash Royale CLAN TAG#URR8PPP
$begingroup$
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
$endgroup$
add a comment |
$begingroup$
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
$endgroup$
1
$begingroup$
Seeing as your answer is a negative number, probably not.
$endgroup$
– bof
Jan 4 at 5:08
$begingroup$
I am double counting something then...
$endgroup$
– Gimgim
Jan 4 at 5:09
$begingroup$
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.
$endgroup$
– jmerry
Jan 4 at 5:40
$begingroup$
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
$endgroup$
– bof
Jan 4 at 5:49
$begingroup$
What does "can be made" mean?
$endgroup$
– DanielV
Jan 4 at 10:05
add a comment |
$begingroup$
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
$endgroup$
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 Jan 4 at 6:03
Gimgim
asked Jan 4 at 5:03
GimgimGimgim
1869
1869
1
$begingroup$
Seeing as your answer is a negative number, probably not.
$endgroup$
– bof
Jan 4 at 5:08
$begingroup$
I am double counting something then...
$endgroup$
– Gimgim
Jan 4 at 5:09
$begingroup$
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.
$endgroup$
– jmerry
Jan 4 at 5:40
$begingroup$
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
$endgroup$
– bof
Jan 4 at 5:49
$begingroup$
What does "can be made" mean?
$endgroup$
– DanielV
Jan 4 at 10:05
add a comment |
1
$begingroup$
Seeing as your answer is a negative number, probably not.
$endgroup$
– bof
Jan 4 at 5:08
$begingroup$
I am double counting something then...
$endgroup$
– Gimgim
Jan 4 at 5:09
$begingroup$
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.
$endgroup$
– jmerry
Jan 4 at 5:40
$begingroup$
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
$endgroup$
– bof
Jan 4 at 5:49
$begingroup$
What does "can be made" mean?
$endgroup$
– DanielV
Jan 4 at 10:05
1
1
$begingroup$
Seeing as your answer is a negative number, probably not.
$endgroup$
– bof
Jan 4 at 5:08
$begingroup$
Seeing as your answer is a negative number, probably not.
$endgroup$
– bof
Jan 4 at 5:08
$begingroup$
I am double counting something then...
$endgroup$
– Gimgim
Jan 4 at 5:09
$begingroup$
I am double counting something then...
$endgroup$
– Gimgim
Jan 4 at 5:09
$begingroup$
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.
$endgroup$
– jmerry
Jan 4 at 5:40
$begingroup$
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.
$endgroup$
– jmerry
Jan 4 at 5:40
$begingroup$
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
$endgroup$
– bof
Jan 4 at 5:49
$begingroup$
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
$endgroup$
– bof
Jan 4 at 5:49
$begingroup$
What does "can be made" mean?
$endgroup$
– DanielV
Jan 4 at 10:05
$begingroup$
What does "can be made" mean?
$endgroup$
– DanielV
Jan 4 at 10:05
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
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.
$endgroup$
$begingroup$
Ohhh! yes!! I didn't think in that way
$endgroup$
– Gimgim
Jan 4 at 5:54
add a comment |
$begingroup$
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.
$endgroup$
$begingroup$
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
$endgroup$
– bof
Jan 4 at 6:04
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
$begingroup$
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.
$endgroup$
$begingroup$
Ohhh! yes!! I didn't think in that way
$endgroup$
– Gimgim
Jan 4 at 5:54
add a comment |
$begingroup$
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.
$endgroup$
$begingroup$
Ohhh! yes!! I didn't think in that way
$endgroup$
– Gimgim
Jan 4 at 5:54
add a comment |
$begingroup$
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.
$endgroup$
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.
edited Jan 4 at 10:02
answered Jan 4 at 5:45
bofbof
51k457120
51k457120
$begingroup$
Ohhh! yes!! I didn't think in that way
$endgroup$
– Gimgim
Jan 4 at 5:54
add a comment |
$begingroup$
Ohhh! yes!! I didn't think in that way
$endgroup$
– Gimgim
Jan 4 at 5:54
$begingroup$
Ohhh! yes!! I didn't think in that way
$endgroup$
– Gimgim
Jan 4 at 5:54
$begingroup$
Ohhh! yes!! I didn't think in that way
$endgroup$
– Gimgim
Jan 4 at 5:54
add a comment |
$begingroup$
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.
$endgroup$
$begingroup$
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
$endgroup$
– bof
Jan 4 at 6:04
add a comment |
$begingroup$
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.
$endgroup$
$begingroup$
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
$endgroup$
– bof
Jan 4 at 6:04
add a comment |
$begingroup$
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.
$endgroup$
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.
edited Jan 4 at 6:06
Gimgim
1869
1869
answered Jan 4 at 6:00
Erik ParkinsonErik Parkinson
8549
8549
$begingroup$
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
$endgroup$
– bof
Jan 4 at 6:04
add a comment |
$begingroup$
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
$endgroup$
– bof
Jan 4 at 6:04
$begingroup$
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
$endgroup$
– bof
Jan 4 at 6:04
$begingroup$
Right. I didn't notice that you posted this answer while I was typing the P.S. to my answer.
$endgroup$
– bof
Jan 4 at 6:04
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%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
$begingroup$
Seeing as your answer is a negative number, probably not.
$endgroup$
– bof
Jan 4 at 5:08
$begingroup$
I am double counting something then...
$endgroup$
– Gimgim
Jan 4 at 5:09
$begingroup$
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.
$endgroup$
– jmerry
Jan 4 at 5:40
$begingroup$
@jmerry And $7$ points for $7$ triangles, and $9$ points for $12$ triangles, Steiner triple systems.
$endgroup$
– bof
Jan 4 at 5:49
$begingroup$
What does "can be made" mean?
$endgroup$
– DanielV
Jan 4 at 10:05