Line in a plane, so that it intersects all previously existing lines but no previously existing intersections...
I don't know what this has to do with combinatorics, but it appeared in an exam last year.
In a plane, $n$ lines should be drawn, so that the amount of resulting areas are maximal. The amount of resulting areas is denoted as $L_n$
How can one show, that the following is possible?
A line can be drawn in the plane, so that it intersects all the previously existing lines. At the same time it should not intersect with previously existing intersections. (Meaning that all intersections of the line with already existing lines should be different)
So I thought that it could look like below and then the next line, f.ex. $h$ would intersect $g$ and the next line, f.ex. $i$ should intersect both $h$ and $g$ without intersecting any previous existing intersections.
But I don't know how to write this formally and how to find a recursion formula for $L_n$.
combinatorics recursion
asked Nov 29 at 20:30
Math Dummy
276
add a comment |
I don't know what this has to do with combinatorics, but it appeared in an exam last year.
In a plane, $n$ lines should be drawn, so that the amount of resulting areas are maximal. The amount of resulting areas is denoted as $L_n$
How can one show, that the following is possible?
A line can be drawn in the plane, so that it intersects all the previously existing lines. At the same time it should not intersect with previously existing intersections. (Meaning that all intersections of the line with already existing lines should be different)
So I thought that it could look like below and then the next line, f.ex. $h$ would intersect $g$ and the next line, f.ex. $i$ should intersect both $h$ and $g$ without intersecting any previous existing intersections.
But I don't know how to write this formally and how to find a recursion formula for $L_n$.
combinatorics recursion
asked Nov 29 at 20:30
Math Dummy
276
Proof by induction. Show that it is true in some base case. If it is true for some number $n$, show that one additional line can always be added to the plane.
– Doug M
Nov 29 at 20:42
add a comment |
I don't know what this has to do with combinatorics, but it appeared in an exam last year.
In a plane, $n$ lines should be drawn, so that the amount of resulting areas are maximal. The amount of resulting areas is denoted as $L_n$
How can one show, that the following is possible?
A line can be drawn in the plane, so that it intersects all the previously existing lines. At the same time it should not intersect with previously existing intersections. (Meaning that all intersections of the line with already existing lines should be different)
So I thought that it could look like below and then the next line, f.ex. $h$ would intersect $g$ and the next line, f.ex. $i$ should intersect both $h$ and $g$ without intersecting any previous existing intersections.
But I don't know how to write this formally and how to find a recursion formula for $L_n$.
combinatorics recursion
asked Nov 29 at 20:30
Math Dummy
276
I don't know what this has to do with combinatorics, but it appeared in an exam last year.
In a plane, $n$ lines should be drawn, so that the amount of resulting areas are maximal. The amount of resulting areas is denoted as $L_n$
How can one show, that the following is possible?
A line can be drawn in the plane, so that it intersects all the previously existing lines. At the same time it should not intersect with previously existing intersections. (Meaning that all intersections of the line with already existing lines should be different)
So I thought that it could look like below and then the next line, f.ex. $h$ would intersect $g$ and the next line, f.ex. $i$ should intersect both $h$ and $g$ without intersecting any previous existing intersections.
But I don't know how to write this formally and how to find a recursion formula for $L_n$.
combinatorics recursion
combinatorics recursion
asked Nov 29 at 20:30
Math Dummy
276
asked Nov 29 at 20:30
Math Dummy
276
edited Nov 29 at 20:38
asked Nov 29 at 20:30
Math Dummy
276
asked Nov 29 at 20:30
Math Dummy
276
asked Nov 29 at 20:30
Math Dummy
276
276
Proof by induction. Show that it is true in some base case. If it is true for some number $n$, show that one additional line can always be added to the plane.
– Doug M
Nov 29 at 20:42
add a comment |
Proof by induction. Show that it is true in some base case. If it is true for some number $n$, show that one additional line can always be added to the plane.
– Doug M
Nov 29 at 20:42
Proof by induction. Show that it is true in some base case. If it is true for some number $n$, show that one additional line can always be added to the plane.
– Doug M
Nov 29 at 20:42
Proof by induction. Show that it is true in some base case. If it is true for some number $n$, show that one additional line can always be added to the plane.
– Doug M
Nov 29 at 20:42
add a comment |
1 Answer
1
active
oldest
votes
"Is the following possible?" - Yes. Just note that if you already have $n$ distinct lines in the plane, then you can surely pick a line $ell$ that is not parallel to any of these (because there are infinitely many directions to choose from and only finitely many to avoid). Among the infinitely many parallels to $ell$, there is certainly one that avoids the finitely many intersection points between the previous $n $lines. Take ons such line as line $n+1$.
With the above construction, the new line number $n+1$ will have $n$ distinct intersection points on it, thereby being split into $n+1$ segments (with two of the segments infinite). Each of these segments cuts a region in two. Therefore we have the recursion
$$L_{n+1}=L_n+n+1 $$
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$?
– Math Dummy
Nov 29 at 20:49
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%2f3019167%2fline-in-a-plane-so-that-it-intersects-all-previously-existing-lines-but-no-prev%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
"Is the following possible?" - Yes. Just note that if you already have $n$ distinct lines in the plane, then you can surely pick a line $ell$ that is not parallel to any of these (because there are infinitely many directions to choose from and only finitely many to avoid). Among the infinitely many parallels to $ell$, there is certainly one that avoids the finitely many intersection points between the previous $n $lines. Take ons such line as line $n+1$.
With the above construction, the new line number $n+1$ will have $n$ distinct intersection points on it, thereby being split into $n+1$ segments (with two of the segments infinite). Each of these segments cuts a region in two. Therefore we have the recursion
$$L_{n+1}=L_n+n+1 $$
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$?
– Math Dummy
Nov 29 at 20:49
add a comment |
"Is the following possible?" - Yes. Just note that if you already have $n$ distinct lines in the plane, then you can surely pick a line $ell$ that is not parallel to any of these (because there are infinitely many directions to choose from and only finitely many to avoid). Among the infinitely many parallels to $ell$, there is certainly one that avoids the finitely many intersection points between the previous $n $lines. Take ons such line as line $n+1$.
With the above construction, the new line number $n+1$ will have $n$ distinct intersection points on it, thereby being split into $n+1$ segments (with two of the segments infinite). Each of these segments cuts a region in two. Therefore we have the recursion
$$L_{n+1}=L_n+n+1 $$
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$?
– Math Dummy
Nov 29 at 20:49
add a comment |
"Is the following possible?" - Yes. Just note that if you already have $n$ distinct lines in the plane, then you can surely pick a line $ell$ that is not parallel to any of these (because there are infinitely many directions to choose from and only finitely many to avoid). Among the infinitely many parallels to $ell$, there is certainly one that avoids the finitely many intersection points between the previous $n $lines. Take ons such line as line $n+1$.
With the above construction, the new line number $n+1$ will have $n$ distinct intersection points on it, thereby being split into $n+1$ segments (with two of the segments infinite). Each of these segments cuts a region in two. Therefore we have the recursion
$$L_{n+1}=L_n+n+1 $$
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
"Is the following possible?" - Yes. Just note that if you already have $n$ distinct lines in the plane, then you can surely pick a line $ell$ that is not parallel to any of these (because there are infinitely many directions to choose from and only finitely many to avoid). Among the infinitely many parallels to $ell$, there is certainly one that avoids the finitely many intersection points between the previous $n $lines. Take ons such line as line $n+1$.
With the above construction, the new line number $n+1$ will have $n$ distinct intersection points on it, thereby being split into $n+1$ segments (with two of the segments infinite). Each of these segments cuts a region in two. Therefore we have the recursion
$$L_{n+1}=L_n+n+1 $$
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
answered Nov 29 at 20:42
Hagen von Eitzen
275k21268495
275k21268495
Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$?
– Math Dummy
Nov 29 at 20:49
add a comment |
Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$?
– Math Dummy
Nov 29 at 20:49
Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$?
– Math Dummy
Nov 29 at 20:49
Thank you very much, that helped a lot. Do you also know how one can get a closed form for $L_n$ with the help of $L_{n+1} = L_n + n + 1$?
– Math Dummy
Nov 29 at 20:49
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.
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.
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%2f3019167%2fline-in-a-plane-so-that-it-intersects-all-previously-existing-lines-but-no-prev%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
Proof by induction. Show that it is true in some base case. If it is true for some number $n$, show that one additional line can always be added to the plane.
– Doug M
Nov 29 at 20:42