Mixing
How to show the number of domains the disk is split into is $1+ C_n^2 + C_n^4$?
$begingroup$
Assuming there are n points on a circle, then there are $C_n^2$ chords. If any three chords don't intersect in circle. How to show the circle will be divided into $1+ C_n^2 + C_n^4$ domains?
Picture below is a example of 5 points on circle.
induction
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
$endgroup$
add a comment |
$begingroup$
Assuming there are n points on a circle, then there are $C_n^2$ chords. If any three chords don't intersect in circle. How to show the circle will be divided into $1+ C_n^2 + C_n^4$ domains?
Picture below is a example of 5 points on circle.
induction
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
$endgroup$
1
$begingroup$
Contest math? Can you give a link or otherwise make sure that the contest is not currently running. We have a strict policy not to discuss on-going contests
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:13
$begingroup$
Anyway, I would try induction on $n$. Add another point, draw the new chords, and for each and every one of them determine how many other chords it intersects with. Then determine how many "old" regions are split in two by the "new" chords and apply the induction hypothesis. I haven't done the details. Possibly familiarity with standard summation formulas is required. In other words, adapt this thinking to your case.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:18
$begingroup$
Not ruling out the possibility that a sleek answer exists :-) Anyway, if you are in contest training, you are expected to be familiar with (or to familiarize yourself with) that simpler variant.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:21
add a comment |
$begingroup$
Assuming there are n points on a circle, then there are $C_n^2$ chords. If any three chords don't intersect in circle. How to show the circle will be divided into $1+ C_n^2 + C_n^4$ domains?
Picture below is a example of 5 points on circle.
induction
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
$endgroup$
Assuming there are n points on a circle, then there are $C_n^2$ chords. If any three chords don't intersect in circle. How to show the circle will be divided into $1+ C_n^2 + C_n^4$ domains?
Picture below is a example of 5 points on circle.
induction
induction
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
edited Jan 3 at 10:45
lanse7pty
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
asked Jan 3 at 9:02
lanse7ptylanse7pty
1,7841823
1,7841823
1
$begingroup$
Contest math? Can you give a link or otherwise make sure that the contest is not currently running. We have a strict policy not to discuss on-going contests
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:13
$begingroup$
Anyway, I would try induction on $n$. Add another point, draw the new chords, and for each and every one of them determine how many other chords it intersects with. Then determine how many "old" regions are split in two by the "new" chords and apply the induction hypothesis. I haven't done the details. Possibly familiarity with standard summation formulas is required. In other words, adapt this thinking to your case.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:18
$begingroup$
Not ruling out the possibility that a sleek answer exists :-) Anyway, if you are in contest training, you are expected to be familiar with (or to familiarize yourself with) that simpler variant.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:21
add a comment |
1
$begingroup$
Contest math? Can you give a link or otherwise make sure that the contest is not currently running. We have a strict policy not to discuss on-going contests
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:13
$begingroup$
Anyway, I would try induction on $n$. Add another point, draw the new chords, and for each and every one of them determine how many other chords it intersects with. Then determine how many "old" regions are split in two by the "new" chords and apply the induction hypothesis. I haven't done the details. Possibly familiarity with standard summation formulas is required. In other words, adapt this thinking to your case.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:18
$begingroup$
Not ruling out the possibility that a sleek answer exists :-) Anyway, if you are in contest training, you are expected to be familiar with (or to familiarize yourself with) that simpler variant.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:21
1
1
$begingroup$
Contest math? Can you give a link or otherwise make sure that the contest is not currently running. We have a strict policy not to discuss on-going contests
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:13
$begingroup$
Contest math? Can you give a link or otherwise make sure that the contest is not currently running. We have a strict policy not to discuss on-going contests
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:13
$begingroup$
Anyway, I would try induction on $n$. Add another point, draw the new chords, and for each and every one of them determine how many other chords it intersects with. Then determine how many "old" regions are split in two by the "new" chords and apply the induction hypothesis. I haven't done the details. Possibly familiarity with standard summation formulas is required. In other words, adapt this thinking to your case.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:18
$begingroup$
Anyway, I would try induction on $n$. Add another point, draw the new chords, and for each and every one of them determine how many other chords it intersects with. Then determine how many "old" regions are split in two by the "new" chords and apply the induction hypothesis. I haven't done the details. Possibly familiarity with standard summation formulas is required. In other words, adapt this thinking to your case.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:18
$begingroup$
Not ruling out the possibility that a sleek answer exists :-) Anyway, if you are in contest training, you are expected to be familiar with (or to familiarize yourself with) that simpler variant.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:21
$begingroup$
Not ruling out the possibility that a sleek answer exists :-) Anyway, if you are in contest training, you are expected to be familiar with (or to familiarize yourself with) that simpler variant.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:21
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Induction proof
Base step: For a single point, there is only one region. This is what the formula $1 + binom 12 + binom 14$ says as well, so we're good.
Induction step: Say the formula is correct for $n = k$. Now take the figure for $k$ points, and add another point. How many new regions did we make? Well, for each of the $k$ new chords we draw, we can find out how many regions it cut into two new regions, and add them together.
Below is a picture for $k = 5$, with old points in red, old chords in blue, the new point in green (the lowest one), and the new chords in purple.
How many regions does one of the new chords divide? If you look at the drawing you can convince yourself that it's the number of old chords it intersects (not counting the chords that share an end point) plus 1. And the new chord intersects an old chord if and only if the end points of the old chord are on opposite sides of the new chord. So the number of old chords that a new chord intersects is simply the number of old points to its left multiplied by the number of points to its right (again, not including its end point).
Let's label the new chords $1$ through $k$, from left to right. As an example, chord number $1$ (the leftmost new chord) has no old points on its left and four on its right, so it intersects $0cdot 4 = 0$ chords and therefore makes $0 + 1$ new regions. Chord number $3$, on the other hand (the middle new chord), has two old points on its left and two new points on its right, and therefore intersects $2cdot 2 = 4$ chords, meaning it makes $4+1 = 5$ new regions. In general, for chord number $i$, there are $i-1$ old points on its left and $k-i$ old points on its right, so it intersects $(i-1)(k-i)$ chords and thus makes $(i-1)(k-i) + 1$ new regions.
Thus the number of regions for $n = k+1$ is
$$
1 + binom k2 + binom k4 + sum_{i = 1}^k big[ (i-1)(k-i) + 1 big]\
= 1 + binom k2 + binom k4 + sum_{i = 1}^k(ik - i^2 - k + i + 1)\
= 1 + binom k2 + binom k4 + kbinom {k + 1}2 - frac{k(k+1)(2k+1)}{6} - k^2 + binom {k+1}2 + k
$$
where I've used the well-known formulas for sums of consecutive integers and sums of consecutive squares. In here we have $1$ and we have a $binom{k+1}2$, so for this to be equal to what we want, namely $1 + binom{k+1}2 + binom{k+1}4$, the only thing left is to prove that the remaining terms match up. In other words that
$$
binom k2 + binom k4 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom{k+1}4
$$
Here one can just insert, calculate and check. Or one can simplify a bit first, using $binom{k+1}4 = binom k3 + binom k4$, and then insert and calculate:
$$
binom {k}2 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom k3\
frac{k^2 - k}2 + frac{k^3+k^2}{2} - frac{2k^3+3k^2 + k}{6} - k^2 + k= frac{k^3 - 3k^2 + 2k}{6}
$$
Confirming that this is indeed true is not very difficult.
Alternative proof
This problem also has a nice solution using the Euler characteristic. I'll give a summary of the solution in that video here.
Your drawing is a planar graph, where the original $n$ points, along with any intersection between chords are the vertices, and all the resulting line segments from intersection to intersection, as well as the cicrle arcs between the original points, are the edges. Euler's characteristic formula then says that $F$, the number of regions inside your circle, is
$$
F = E - V + 1
$$
where $V$ is the number of vertices and $E$ is the number of edges. (Note that in the Wikipedia article and the video I linked above, the region outside the circle is also counted, which is why they have $+2$ at the end instead of $+1$. We don't want to count that one, so I threw it out from the get-go.)
So, how many vertices and edges do we have?
I'll start with the number vertices. First there are the original $n$ points. in addition there are all th intersections between the chords. How many intersections are there? Well, there is exactly one intersection for each quadruple of originaal points. So that's $binom n4$. In total we get $V = n + binom n4$.
Then the number of edges. First there are $n$ circle arcs. Then there are the $binom n2$ chords, which are chopped up. How are they chopped up? Note that each intersection divides two segments into four, increasing the total number of segments by $2$. So there are $binom n2 + 2binom n4$ line segments. In total $E = n + binom n2 + 2binom n4$.
Inserting that into Euler's formula above, we get
$$
F = binom n4 + binom n2 + 1
$$
which is what we were after.
answered Jan 3 at 10:32
ArthurArthur
112k7108191
$endgroup$
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%2f3060383%2fhow-to-show-the-number-of-domains-the-disk-is-split-into-is-1-c-n2-c-n4%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Induction proof
Base step: For a single point, there is only one region. This is what the formula $1 + binom 12 + binom 14$ says as well, so we're good.
Induction step: Say the formula is correct for $n = k$. Now take the figure for $k$ points, and add another point. How many new regions did we make? Well, for each of the $k$ new chords we draw, we can find out how many regions it cut into two new regions, and add them together.
Below is a picture for $k = 5$, with old points in red, old chords in blue, the new point in green (the lowest one), and the new chords in purple.
How many regions does one of the new chords divide? If you look at the drawing you can convince yourself that it's the number of old chords it intersects (not counting the chords that share an end point) plus 1. And the new chord intersects an old chord if and only if the end points of the old chord are on opposite sides of the new chord. So the number of old chords that a new chord intersects is simply the number of old points to its left multiplied by the number of points to its right (again, not including its end point).
Let's label the new chords $1$ through $k$, from left to right. As an example, chord number $1$ (the leftmost new chord) has no old points on its left and four on its right, so it intersects $0cdot 4 = 0$ chords and therefore makes $0 + 1$ new regions. Chord number $3$, on the other hand (the middle new chord), has two old points on its left and two new points on its right, and therefore intersects $2cdot 2 = 4$ chords, meaning it makes $4+1 = 5$ new regions. In general, for chord number $i$, there are $i-1$ old points on its left and $k-i$ old points on its right, so it intersects $(i-1)(k-i)$ chords and thus makes $(i-1)(k-i) + 1$ new regions.
Thus the number of regions for $n = k+1$ is
$$
1 + binom k2 + binom k4 + sum_{i = 1}^k big[ (i-1)(k-i) + 1 big]\
= 1 + binom k2 + binom k4 + sum_{i = 1}^k(ik - i^2 - k + i + 1)\
= 1 + binom k2 + binom k4 + kbinom {k + 1}2 - frac{k(k+1)(2k+1)}{6} - k^2 + binom {k+1}2 + k
$$
where I've used the well-known formulas for sums of consecutive integers and sums of consecutive squares. In here we have $1$ and we have a $binom{k+1}2$, so for this to be equal to what we want, namely $1 + binom{k+1}2 + binom{k+1}4$, the only thing left is to prove that the remaining terms match up. In other words that
$$
binom k2 + binom k4 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom{k+1}4
$$
Here one can just insert, calculate and check. Or one can simplify a bit first, using $binom{k+1}4 = binom k3 + binom k4$, and then insert and calculate:
$$
binom {k}2 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom k3\
frac{k^2 - k}2 + frac{k^3+k^2}{2} - frac{2k^3+3k^2 + k}{6} - k^2 + k= frac{k^3 - 3k^2 + 2k}{6}
$$
Confirming that this is indeed true is not very difficult.
Alternative proof
This problem also has a nice solution using the Euler characteristic. I'll give a summary of the solution in that video here.
Your drawing is a planar graph, where the original $n$ points, along with any intersection between chords are the vertices, and all the resulting line segments from intersection to intersection, as well as the cicrle arcs between the original points, are the edges. Euler's characteristic formula then says that $F$, the number of regions inside your circle, is
$$
F = E - V + 1
$$
where $V$ is the number of vertices and $E$ is the number of edges. (Note that in the Wikipedia article and the video I linked above, the region outside the circle is also counted, which is why they have $+2$ at the end instead of $+1$. We don't want to count that one, so I threw it out from the get-go.)
So, how many vertices and edges do we have?
I'll start with the number vertices. First there are the original $n$ points. in addition there are all th intersections between the chords. How many intersections are there? Well, there is exactly one intersection for each quadruple of originaal points. So that's $binom n4$. In total we get $V = n + binom n4$.
Then the number of edges. First there are $n$ circle arcs. Then there are the $binom n2$ chords, which are chopped up. How are they chopped up? Note that each intersection divides two segments into four, increasing the total number of segments by $2$. So there are $binom n2 + 2binom n4$ line segments. In total $E = n + binom n2 + 2binom n4$.
Inserting that into Euler's formula above, we get
$$
F = binom n4 + binom n2 + 1
$$
which is what we were after.
answered Jan 3 at 10:32
ArthurArthur
112k7108191
$endgroup$
add a comment |
$begingroup$
Induction proof
Base step: For a single point, there is only one region. This is what the formula $1 + binom 12 + binom 14$ says as well, so we're good.
Induction step: Say the formula is correct for $n = k$. Now take the figure for $k$ points, and add another point. How many new regions did we make? Well, for each of the $k$ new chords we draw, we can find out how many regions it cut into two new regions, and add them together.
Below is a picture for $k = 5$, with old points in red, old chords in blue, the new point in green (the lowest one), and the new chords in purple.
How many regions does one of the new chords divide? If you look at the drawing you can convince yourself that it's the number of old chords it intersects (not counting the chords that share an end point) plus 1. And the new chord intersects an old chord if and only if the end points of the old chord are on opposite sides of the new chord. So the number of old chords that a new chord intersects is simply the number of old points to its left multiplied by the number of points to its right (again, not including its end point).
Let's label the new chords $1$ through $k$, from left to right. As an example, chord number $1$ (the leftmost new chord) has no old points on its left and four on its right, so it intersects $0cdot 4 = 0$ chords and therefore makes $0 + 1$ new regions. Chord number $3$, on the other hand (the middle new chord), has two old points on its left and two new points on its right, and therefore intersects $2cdot 2 = 4$ chords, meaning it makes $4+1 = 5$ new regions. In general, for chord number $i$, there are $i-1$ old points on its left and $k-i$ old points on its right, so it intersects $(i-1)(k-i)$ chords and thus makes $(i-1)(k-i) + 1$ new regions.
Thus the number of regions for $n = k+1$ is
$$
1 + binom k2 + binom k4 + sum_{i = 1}^k big[ (i-1)(k-i) + 1 big]\
= 1 + binom k2 + binom k4 + sum_{i = 1}^k(ik - i^2 - k + i + 1)\
= 1 + binom k2 + binom k4 + kbinom {k + 1}2 - frac{k(k+1)(2k+1)}{6} - k^2 + binom {k+1}2 + k
$$
where I've used the well-known formulas for sums of consecutive integers and sums of consecutive squares. In here we have $1$ and we have a $binom{k+1}2$, so for this to be equal to what we want, namely $1 + binom{k+1}2 + binom{k+1}4$, the only thing left is to prove that the remaining terms match up. In other words that
$$
binom k2 + binom k4 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom{k+1}4
$$
Here one can just insert, calculate and check. Or one can simplify a bit first, using $binom{k+1}4 = binom k3 + binom k4$, and then insert and calculate:
$$
binom {k}2 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom k3\
frac{k^2 - k}2 + frac{k^3+k^2}{2} - frac{2k^3+3k^2 + k}{6} - k^2 + k= frac{k^3 - 3k^2 + 2k}{6}
$$
Confirming that this is indeed true is not very difficult.
Alternative proof
This problem also has a nice solution using the Euler characteristic. I'll give a summary of the solution in that video here.
Your drawing is a planar graph, where the original $n$ points, along with any intersection between chords are the vertices, and all the resulting line segments from intersection to intersection, as well as the cicrle arcs between the original points, are the edges. Euler's characteristic formula then says that $F$, the number of regions inside your circle, is
$$
F = E - V + 1
$$
where $V$ is the number of vertices and $E$ is the number of edges. (Note that in the Wikipedia article and the video I linked above, the region outside the circle is also counted, which is why they have $+2$ at the end instead of $+1$. We don't want to count that one, so I threw it out from the get-go.)
So, how many vertices and edges do we have?
I'll start with the number vertices. First there are the original $n$ points. in addition there are all th intersections between the chords. How many intersections are there? Well, there is exactly one intersection for each quadruple of originaal points. So that's $binom n4$. In total we get $V = n + binom n4$.
Then the number of edges. First there are $n$ circle arcs. Then there are the $binom n2$ chords, which are chopped up. How are they chopped up? Note that each intersection divides two segments into four, increasing the total number of segments by $2$. So there are $binom n2 + 2binom n4$ line segments. In total $E = n + binom n2 + 2binom n4$.
Inserting that into Euler's formula above, we get
$$
F = binom n4 + binom n2 + 1
$$
which is what we were after.
answered Jan 3 at 10:32
ArthurArthur
112k7108191
$endgroup$
add a comment |
$begingroup$
Induction proof
Base step: For a single point, there is only one region. This is what the formula $1 + binom 12 + binom 14$ says as well, so we're good.
Induction step: Say the formula is correct for $n = k$. Now take the figure for $k$ points, and add another point. How many new regions did we make? Well, for each of the $k$ new chords we draw, we can find out how many regions it cut into two new regions, and add them together.
Below is a picture for $k = 5$, with old points in red, old chords in blue, the new point in green (the lowest one), and the new chords in purple.
How many regions does one of the new chords divide? If you look at the drawing you can convince yourself that it's the number of old chords it intersects (not counting the chords that share an end point) plus 1. And the new chord intersects an old chord if and only if the end points of the old chord are on opposite sides of the new chord. So the number of old chords that a new chord intersects is simply the number of old points to its left multiplied by the number of points to its right (again, not including its end point).
Let's label the new chords $1$ through $k$, from left to right. As an example, chord number $1$ (the leftmost new chord) has no old points on its left and four on its right, so it intersects $0cdot 4 = 0$ chords and therefore makes $0 + 1$ new regions. Chord number $3$, on the other hand (the middle new chord), has two old points on its left and two new points on its right, and therefore intersects $2cdot 2 = 4$ chords, meaning it makes $4+1 = 5$ new regions. In general, for chord number $i$, there are $i-1$ old points on its left and $k-i$ old points on its right, so it intersects $(i-1)(k-i)$ chords and thus makes $(i-1)(k-i) + 1$ new regions.
Thus the number of regions for $n = k+1$ is
$$
1 + binom k2 + binom k4 + sum_{i = 1}^k big[ (i-1)(k-i) + 1 big]\
= 1 + binom k2 + binom k4 + sum_{i = 1}^k(ik - i^2 - k + i + 1)\
= 1 + binom k2 + binom k4 + kbinom {k + 1}2 - frac{k(k+1)(2k+1)}{6} - k^2 + binom {k+1}2 + k
$$
where I've used the well-known formulas for sums of consecutive integers and sums of consecutive squares. In here we have $1$ and we have a $binom{k+1}2$, so for this to be equal to what we want, namely $1 + binom{k+1}2 + binom{k+1}4$, the only thing left is to prove that the remaining terms match up. In other words that
$$
binom k2 + binom k4 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom{k+1}4
$$
Here one can just insert, calculate and check. Or one can simplify a bit first, using $binom{k+1}4 = binom k3 + binom k4$, and then insert and calculate:
$$
binom {k}2 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom k3\
frac{k^2 - k}2 + frac{k^3+k^2}{2} - frac{2k^3+3k^2 + k}{6} - k^2 + k= frac{k^3 - 3k^2 + 2k}{6}
$$
Confirming that this is indeed true is not very difficult.
Alternative proof
This problem also has a nice solution using the Euler characteristic. I'll give a summary of the solution in that video here.
Your drawing is a planar graph, where the original $n$ points, along with any intersection between chords are the vertices, and all the resulting line segments from intersection to intersection, as well as the cicrle arcs between the original points, are the edges. Euler's characteristic formula then says that $F$, the number of regions inside your circle, is
$$
F = E - V + 1
$$
where $V$ is the number of vertices and $E$ is the number of edges. (Note that in the Wikipedia article and the video I linked above, the region outside the circle is also counted, which is why they have $+2$ at the end instead of $+1$. We don't want to count that one, so I threw it out from the get-go.)
So, how many vertices and edges do we have?
I'll start with the number vertices. First there are the original $n$ points. in addition there are all th intersections between the chords. How many intersections are there? Well, there is exactly one intersection for each quadruple of originaal points. So that's $binom n4$. In total we get $V = n + binom n4$.
Then the number of edges. First there are $n$ circle arcs. Then there are the $binom n2$ chords, which are chopped up. How are they chopped up? Note that each intersection divides two segments into four, increasing the total number of segments by $2$. So there are $binom n2 + 2binom n4$ line segments. In total $E = n + binom n2 + 2binom n4$.
Inserting that into Euler's formula above, we get
$$
F = binom n4 + binom n2 + 1
$$
which is what we were after.
answered Jan 3 at 10:32
ArthurArthur
112k7108191
$endgroup$
Induction proof
Base step: For a single point, there is only one region. This is what the formula $1 + binom 12 + binom 14$ says as well, so we're good.
Induction step: Say the formula is correct for $n = k$. Now take the figure for $k$ points, and add another point. How many new regions did we make? Well, for each of the $k$ new chords we draw, we can find out how many regions it cut into two new regions, and add them together.
Below is a picture for $k = 5$, with old points in red, old chords in blue, the new point in green (the lowest one), and the new chords in purple.
How many regions does one of the new chords divide? If you look at the drawing you can convince yourself that it's the number of old chords it intersects (not counting the chords that share an end point) plus 1. And the new chord intersects an old chord if and only if the end points of the old chord are on opposite sides of the new chord. So the number of old chords that a new chord intersects is simply the number of old points to its left multiplied by the number of points to its right (again, not including its end point).
Let's label the new chords $1$ through $k$, from left to right. As an example, chord number $1$ (the leftmost new chord) has no old points on its left and four on its right, so it intersects $0cdot 4 = 0$ chords and therefore makes $0 + 1$ new regions. Chord number $3$, on the other hand (the middle new chord), has two old points on its left and two new points on its right, and therefore intersects $2cdot 2 = 4$ chords, meaning it makes $4+1 = 5$ new regions. In general, for chord number $i$, there are $i-1$ old points on its left and $k-i$ old points on its right, so it intersects $(i-1)(k-i)$ chords and thus makes $(i-1)(k-i) + 1$ new regions.
Thus the number of regions for $n = k+1$ is
$$
1 + binom k2 + binom k4 + sum_{i = 1}^k big[ (i-1)(k-i) + 1 big]\
= 1 + binom k2 + binom k4 + sum_{i = 1}^k(ik - i^2 - k + i + 1)\
= 1 + binom k2 + binom k4 + kbinom {k + 1}2 - frac{k(k+1)(2k+1)}{6} - k^2 + binom {k+1}2 + k
$$
where I've used the well-known formulas for sums of consecutive integers and sums of consecutive squares. In here we have $1$ and we have a $binom{k+1}2$, so for this to be equal to what we want, namely $1 + binom{k+1}2 + binom{k+1}4$, the only thing left is to prove that the remaining terms match up. In other words that
$$
binom k2 + binom k4 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom{k+1}4
$$
Here one can just insert, calculate and check. Or one can simplify a bit first, using $binom{k+1}4 = binom k3 + binom k4$, and then insert and calculate:
$$
binom {k}2 + kbinom {k+1}2 - frac{k(k+1)(2k+1)}6 - k^2 + k= binom k3\
frac{k^2 - k}2 + frac{k^3+k^2}{2} - frac{2k^3+3k^2 + k}{6} - k^2 + k= frac{k^3 - 3k^2 + 2k}{6}
$$
Confirming that this is indeed true is not very difficult.
Alternative proof
This problem also has a nice solution using the Euler characteristic. I'll give a summary of the solution in that video here.
Your drawing is a planar graph, where the original $n$ points, along with any intersection between chords are the vertices, and all the resulting line segments from intersection to intersection, as well as the cicrle arcs between the original points, are the edges. Euler's characteristic formula then says that $F$, the number of regions inside your circle, is
$$
F = E - V + 1
$$
where $V$ is the number of vertices and $E$ is the number of edges. (Note that in the Wikipedia article and the video I linked above, the region outside the circle is also counted, which is why they have $+2$ at the end instead of $+1$. We don't want to count that one, so I threw it out from the get-go.)
So, how many vertices and edges do we have?
I'll start with the number vertices. First there are the original $n$ points. in addition there are all th intersections between the chords. How many intersections are there? Well, there is exactly one intersection for each quadruple of originaal points. So that's $binom n4$. In total we get $V = n + binom n4$.
Then the number of edges. First there are $n$ circle arcs. Then there are the $binom n2$ chords, which are chopped up. How are they chopped up? Note that each intersection divides two segments into four, increasing the total number of segments by $2$. So there are $binom n2 + 2binom n4$ line segments. In total $E = n + binom n2 + 2binom n4$.
Inserting that into Euler's formula above, we get
$$
F = binom n4 + binom n2 + 1
$$
which is what we were after.
answered Jan 3 at 10:32
ArthurArthur
112k7108191
answered Jan 3 at 10:32
ArthurArthur
112k7108191
answered Jan 3 at 10:32
ArthurArthur
112k7108191
answered Jan 3 at 10:32
ArthurArthur
112k7108191
112k7108191
add a comment |
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%2f3060383%2fhow-to-show-the-number-of-domains-the-disk-is-split-into-is-1-c-n2-c-n4%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$
Contest math? Can you give a link or otherwise make sure that the contest is not currently running. We have a strict policy not to discuss on-going contests
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:13
$begingroup$
Anyway, I would try induction on $n$. Add another point, draw the new chords, and for each and every one of them determine how many other chords it intersects with. Then determine how many "old" regions are split in two by the "new" chords and apply the induction hypothesis. I haven't done the details. Possibly familiarity with standard summation formulas is required. In other words, adapt this thinking to your case.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:18
$begingroup$
Not ruling out the possibility that a sleek answer exists :-) Anyway, if you are in contest training, you are expected to be familiar with (or to familiarize yourself with) that simpler variant.
$endgroup$
– Jyrki Lahtonen
Jan 3 at 9:21