$n$ lines in a plane, proper coloring of intersection points with just 3 colors
Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point.
Each intersection point is colored red, green or blue. Prove that it is possible to color all intersection points in a “proper” way, so that any two adjacent points (like $A_i, A_j$) have different colors.
This also means that if you "travel" along an arbitrary line, you will cross $n-1$ intersection points, constantly changing colors from one intersection point to another.
My first (and last) try was to use induction. Obviously for two or three lines, we have one or three intersection points and with three colors available we have the base of induction proved. However, the induction step is more difficult. I was able to prove the induction step if in every possible arrangement of lines it was possible to find a line that divides the plane into two halves with one half having no intersection points. However, I was able to construct counter-examples where such line does not exist.
The last time I tried to solve a similar red-green-blue problem I discovered Ramsey theory. I wonder what I will discover this time :)
combinatorics graph-theory coloring plane-geometry
asked Nov 24 at 22:30
Oldboy
6,8021830
add a comment |
Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point.
Each intersection point is colored red, green or blue. Prove that it is possible to color all intersection points in a “proper” way, so that any two adjacent points (like $A_i, A_j$) have different colors.
This also means that if you "travel" along an arbitrary line, you will cross $n-1$ intersection points, constantly changing colors from one intersection point to another.
My first (and last) try was to use induction. Obviously for two or three lines, we have one or three intersection points and with three colors available we have the base of induction proved. However, the induction step is more difficult. I was able to prove the induction step if in every possible arrangement of lines it was possible to find a line that divides the plane into two halves with one half having no intersection points. However, I was able to construct counter-examples where such line does not exist.
The last time I tried to solve a similar red-green-blue problem I discovered Ramsey theory. I wonder what I will discover this time :)
combinatorics graph-theory coloring plane-geometry
asked Nov 24 at 22:30
Oldboy
6,8021830
add a comment |
Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point.
Each intersection point is colored red, green or blue. Prove that it is possible to color all intersection points in a “proper” way, so that any two adjacent points (like $A_i, A_j$) have different colors.
This also means that if you "travel" along an arbitrary line, you will cross $n-1$ intersection points, constantly changing colors from one intersection point to another.
My first (and last) try was to use induction. Obviously for two or three lines, we have one or three intersection points and with three colors available we have the base of induction proved. However, the induction step is more difficult. I was able to prove the induction step if in every possible arrangement of lines it was possible to find a line that divides the plane into two halves with one half having no intersection points. However, I was able to construct counter-examples where such line does not exist.
The last time I tried to solve a similar red-green-blue problem I discovered Ramsey theory. I wonder what I will discover this time :)
combinatorics graph-theory coloring plane-geometry
asked Nov 24 at 22:30
Oldboy
6,8021830
Draw $n$ lines in a plane so that there are no parallel lines and there are no three lines passing through the same point.
Each intersection point is colored red, green or blue. Prove that it is possible to color all intersection points in a “proper” way, so that any two adjacent points (like $A_i, A_j$) have different colors.
This also means that if you "travel" along an arbitrary line, you will cross $n-1$ intersection points, constantly changing colors from one intersection point to another.
My first (and last) try was to use induction. Obviously for two or three lines, we have one or three intersection points and with three colors available we have the base of induction proved. However, the induction step is more difficult. I was able to prove the induction step if in every possible arrangement of lines it was possible to find a line that divides the plane into two halves with one half having no intersection points. However, I was able to construct counter-examples where such line does not exist.
The last time I tried to solve a similar red-green-blue problem I discovered Ramsey theory. I wonder what I will discover this time :)
combinatorics graph-theory coloring plane-geometry
combinatorics graph-theory coloring plane-geometry
asked Nov 24 at 22:30
Oldboy
6,8021830
asked Nov 24 at 22:30
Oldboy
6,8021830
edited Nov 25 at 6:51
asked Nov 24 at 22:30
Oldboy
6,8021830
asked Nov 24 at 22:30
Oldboy
6,8021830
asked Nov 24 at 22:30
Oldboy
6,8021830
6,8021830
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Let us assume WLOG that no lines are vertical--if not rotate the plane to make this so [make sure you see that this is indeed possible].
Let us colour the set of points from left to right [no lines are vertical, thus for each line $L$ there is indeed a strict ordering of the points on $L$ from left to right], with the colours 1,2,or 3, as follows.
Colour a leftmost point with the color 1. [As there are only $<n^2$ points there is indeed a leftmost point. Pick one such point arbitrarily]
Let $p$ be a point that satisfies the following: Letting $L_1$ and $L_2$ be the two lines containing $p$ [as only two lines intersect a point there are only two such $L_i$], all points to the left of $p$ on $L_1$ [which recall neither $L_1$ nor $L_2$ is not vertical] have already been colored and all points to the left of $p$ on $L_2$ have already been colored. Then letting $p_i$ be the point immediately to the left of $p$ on $L_i$; $i=1,2$; and writing as $c(p_i)$ the color assigned to $p_i$ for $i=1,2$ [$c(p_i) in {1,2,3}$], let the color $c(p)$ of $p$ be an integer in ${1,2,3}$ that is neither $c(p_1)$ nor $c(p_2)$. [There indeed always exists such a $p$ as long as there are still uncoloured points, as a leftmost point of the points not coloured yet always suffices.]
See for yourself that the above algorithm indeed terminates, and that it also terminates with a proper 3-colouring.
answered Nov 25 at 0:01
Mike
2,894211
1
Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.)
– YiFan
Nov 25 at 0:09
1
The leftmost point not colored yet always suffices
– Mike
Nov 25 at 0:10
3
In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.)
– Misha Lavrov
Nov 25 at 4:21
1
@Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$.
– YiFan
Nov 25 at 5:27
1
Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks.
– Oldboy
Nov 25 at 8:50
|
show 3 more comments
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%2f3012183%2fn-lines-in-a-plane-proper-coloring-of-intersection-points-with-just-3-colors%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
Let us assume WLOG that no lines are vertical--if not rotate the plane to make this so [make sure you see that this is indeed possible].
Let us colour the set of points from left to right [no lines are vertical, thus for each line $L$ there is indeed a strict ordering of the points on $L$ from left to right], with the colours 1,2,or 3, as follows.
Colour a leftmost point with the color 1. [As there are only $<n^2$ points there is indeed a leftmost point. Pick one such point arbitrarily]
Let $p$ be a point that satisfies the following: Letting $L_1$ and $L_2$ be the two lines containing $p$ [as only two lines intersect a point there are only two such $L_i$], all points to the left of $p$ on $L_1$ [which recall neither $L_1$ nor $L_2$ is not vertical] have already been colored and all points to the left of $p$ on $L_2$ have already been colored. Then letting $p_i$ be the point immediately to the left of $p$ on $L_i$; $i=1,2$; and writing as $c(p_i)$ the color assigned to $p_i$ for $i=1,2$ [$c(p_i) in {1,2,3}$], let the color $c(p)$ of $p$ be an integer in ${1,2,3}$ that is neither $c(p_1)$ nor $c(p_2)$. [There indeed always exists such a $p$ as long as there are still uncoloured points, as a leftmost point of the points not coloured yet always suffices.]
See for yourself that the above algorithm indeed terminates, and that it also terminates with a proper 3-colouring.
answered Nov 25 at 0:01
Mike
2,894211
1
Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.)
– YiFan
Nov 25 at 0:09
1
The leftmost point not colored yet always suffices
– Mike
Nov 25 at 0:10
3
In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.)
– Misha Lavrov
Nov 25 at 4:21
1
@Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$.
– YiFan
Nov 25 at 5:27
1
Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks.
– Oldboy
Nov 25 at 8:50
|
show 3 more comments
Let us assume WLOG that no lines are vertical--if not rotate the plane to make this so [make sure you see that this is indeed possible].
Let us colour the set of points from left to right [no lines are vertical, thus for each line $L$ there is indeed a strict ordering of the points on $L$ from left to right], with the colours 1,2,or 3, as follows.
Colour a leftmost point with the color 1. [As there are only $<n^2$ points there is indeed a leftmost point. Pick one such point arbitrarily]
Let $p$ be a point that satisfies the following: Letting $L_1$ and $L_2$ be the two lines containing $p$ [as only two lines intersect a point there are only two such $L_i$], all points to the left of $p$ on $L_1$ [which recall neither $L_1$ nor $L_2$ is not vertical] have already been colored and all points to the left of $p$ on $L_2$ have already been colored. Then letting $p_i$ be the point immediately to the left of $p$ on $L_i$; $i=1,2$; and writing as $c(p_i)$ the color assigned to $p_i$ for $i=1,2$ [$c(p_i) in {1,2,3}$], let the color $c(p)$ of $p$ be an integer in ${1,2,3}$ that is neither $c(p_1)$ nor $c(p_2)$. [There indeed always exists such a $p$ as long as there are still uncoloured points, as a leftmost point of the points not coloured yet always suffices.]
See for yourself that the above algorithm indeed terminates, and that it also terminates with a proper 3-colouring.
answered Nov 25 at 0:01
Mike
2,894211
1
Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.)
– YiFan
Nov 25 at 0:09
1
The leftmost point not colored yet always suffices
– Mike
Nov 25 at 0:10
3
In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.)
– Misha Lavrov
Nov 25 at 4:21
1
@Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$.
– YiFan
Nov 25 at 5:27
1
Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks.
– Oldboy
Nov 25 at 8:50
|
show 3 more comments
Let us assume WLOG that no lines are vertical--if not rotate the plane to make this so [make sure you see that this is indeed possible].
Let us colour the set of points from left to right [no lines are vertical, thus for each line $L$ there is indeed a strict ordering of the points on $L$ from left to right], with the colours 1,2,or 3, as follows.
Colour a leftmost point with the color 1. [As there are only $<n^2$ points there is indeed a leftmost point. Pick one such point arbitrarily]
Let $p$ be a point that satisfies the following: Letting $L_1$ and $L_2$ be the two lines containing $p$ [as only two lines intersect a point there are only two such $L_i$], all points to the left of $p$ on $L_1$ [which recall neither $L_1$ nor $L_2$ is not vertical] have already been colored and all points to the left of $p$ on $L_2$ have already been colored. Then letting $p_i$ be the point immediately to the left of $p$ on $L_i$; $i=1,2$; and writing as $c(p_i)$ the color assigned to $p_i$ for $i=1,2$ [$c(p_i) in {1,2,3}$], let the color $c(p)$ of $p$ be an integer in ${1,2,3}$ that is neither $c(p_1)$ nor $c(p_2)$. [There indeed always exists such a $p$ as long as there are still uncoloured points, as a leftmost point of the points not coloured yet always suffices.]
See for yourself that the above algorithm indeed terminates, and that it also terminates with a proper 3-colouring.
answered Nov 25 at 0:01
Mike
2,894211
Let us assume WLOG that no lines are vertical--if not rotate the plane to make this so [make sure you see that this is indeed possible].
Let us colour the set of points from left to right [no lines are vertical, thus for each line $L$ there is indeed a strict ordering of the points on $L$ from left to right], with the colours 1,2,or 3, as follows.
Colour a leftmost point with the color 1. [As there are only $<n^2$ points there is indeed a leftmost point. Pick one such point arbitrarily]
Let $p$ be a point that satisfies the following: Letting $L_1$ and $L_2$ be the two lines containing $p$ [as only two lines intersect a point there are only two such $L_i$], all points to the left of $p$ on $L_1$ [which recall neither $L_1$ nor $L_2$ is not vertical] have already been colored and all points to the left of $p$ on $L_2$ have already been colored. Then letting $p_i$ be the point immediately to the left of $p$ on $L_i$; $i=1,2$; and writing as $c(p_i)$ the color assigned to $p_i$ for $i=1,2$ [$c(p_i) in {1,2,3}$], let the color $c(p)$ of $p$ be an integer in ${1,2,3}$ that is neither $c(p_1)$ nor $c(p_2)$. [There indeed always exists such a $p$ as long as there are still uncoloured points, as a leftmost point of the points not coloured yet always suffices.]
See for yourself that the above algorithm indeed terminates, and that it also terminates with a proper 3-colouring.
answered Nov 25 at 0:01
Mike
2,894211
edited Nov 25 at 0:22
answered Nov 25 at 0:01
Mike
2,894211
answered Nov 25 at 0:01
Mike
2,894211
answered Nov 25 at 0:01
Mike
2,894211
2,894211
1
Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.)
– YiFan
Nov 25 at 0:09
1
The leftmost point not colored yet always suffices
– Mike
Nov 25 at 0:10
3
In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.)
– Misha Lavrov
Nov 25 at 4:21
1
@Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$.
– YiFan
Nov 25 at 5:27
1
Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks.
– Oldboy
Nov 25 at 8:50
|
show 3 more comments
1
Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.)
– YiFan
Nov 25 at 0:09
1
The leftmost point not colored yet always suffices
– Mike
Nov 25 at 0:10
3
In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.)
– Misha Lavrov
Nov 25 at 4:21
1
@Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$.
– YiFan
Nov 25 at 5:27
1
Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks.
– Oldboy
Nov 25 at 8:50
1
1
Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.)
– YiFan
Nov 25 at 0:09
Don't you need to prove that $p$ always exists after an arbitrary number of steps? (Except when you've already coloured everything, of course.)
– YiFan
Nov 25 at 0:09
1
1
The leftmost point not colored yet always suffices
– Mike
Nov 25 at 0:10
The leftmost point not colored yet always suffices
– Mike
Nov 25 at 0:10
3
3
In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.)
– Misha Lavrov
Nov 25 at 4:21
In other words, we find a vertex ordering such that every vertex is adjacent to at most $2$ vertices that follow it. (In general, a graph with such a vertex ordering is called $2$-degenerate.)
– Misha Lavrov
Nov 25 at 4:21
1
1
@Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$.
– YiFan
Nov 25 at 5:27
@Mike there's a nuance: it is possible that there are no points on either $L_1$ or $L_2$ to the left of the leftmost uncoloured point. The first point you colour, for example. Of course this doesn't actually impact your solution though, since you can just for example set $c(p_1)=1$.
– YiFan
Nov 25 at 5:27
1
1
Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks.
– Oldboy
Nov 25 at 8:50
Actually the proof turned out to be very simple: because it is always possible to avoid vertical lines, you can put all intersection points in a sequence so that the $x$ coordinate is increasing. That sequence is unique, And in that sequence, each point is connected to no more than 2 points earlier in the sequence. So it's always possible to color the point based on colors of connected points coming earlier in the sequence. Accepting the answer now, thanks.
– Oldboy
Nov 25 at 8:50
|
show 3 more comments
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%2f3012183%2fn-lines-in-a-plane-proper-coloring-of-intersection-points-with-just-3-colors%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
