Drawing loops on a sheet of paper
Two people are playing a game, in which each player takes turns drawing closed loops on a sheet of paper. Each new loop must intersect each of the other loops exactly twice. When one player has no moves available, the other player wins.
Is it possible for any of the players to ever win? If yes, how? If not, prove that it is impossible.
game
add a comment |
Two people are playing a game, in which each player takes turns drawing closed loops on a sheet of paper. Each new loop must intersect each of the other loops exactly twice. When one player has no moves available, the other player wins.
Is it possible for any of the players to ever win? If yes, how? If not, prove that it is impossible.
game
Are the loops circles? Or any closed shape?
– Dr Xorile
Dec 10 '18 at 3:14
Any closed shape.
– Stefan
Dec 10 '18 at 3:37
add a comment |
Two people are playing a game, in which each player takes turns drawing closed loops on a sheet of paper. Each new loop must intersect each of the other loops exactly twice. When one player has no moves available, the other player wins.
Is it possible for any of the players to ever win? If yes, how? If not, prove that it is impossible.
game
Two people are playing a game, in which each player takes turns drawing closed loops on a sheet of paper. Each new loop must intersect each of the other loops exactly twice. When one player has no moves available, the other player wins.
Is it possible for any of the players to ever win? If yes, how? If not, prove that it is impossible.
game
game
edited Dec 10 '18 at 0:43
rhsquared
7,35521644
7,35521644
asked Dec 9 '18 at 23:12
Stefan
4446
4446
Are the loops circles? Or any closed shape?
– Dr Xorile
Dec 10 '18 at 3:14
Any closed shape.
– Stefan
Dec 10 '18 at 3:37
add a comment |
Are the loops circles? Or any closed shape?
– Dr Xorile
Dec 10 '18 at 3:14
Any closed shape.
– Stefan
Dec 10 '18 at 3:37
Are the loops circles? Or any closed shape?
– Dr Xorile
Dec 10 '18 at 3:14
Are the loops circles? Or any closed shape?
– Dr Xorile
Dec 10 '18 at 3:14
Any closed shape.
– Stefan
Dec 10 '18 at 3:37
Any closed shape.
– Stefan
Dec 10 '18 at 3:37
add a comment |
3 Answers
3
active
oldest
votes
In theory, neither side can win.
This is because
Each player can follow a strategy of drawing a loop that follows parallel and close to the last loop drawn. The last loop goes through each other loop twice, so if you follow it closely enough your line will do so also. Then just make it switch over twice as you're following it around.
add a comment |
When I read this question, I interpreted "loops" more broadly than seems to have been intended, allowing for the possibility that a loop might cross itself. With this possibility in hand, the argument in Dr Xorile's answer no longer works because
if a loop has N self-intersections then a tiny displacement of that loop must cross the original at least 2N times.
In this broader setting, the answer is
still that the game can never finish
and here is one way to see it:
note first of all that any loop divides the plane into regions that can be coloured with two colours, say red and blue, with no two like-coloured regions adjoining. Now take a look at that last loop (call it L) and consider its relations with earlier loops. As you walk around an earlier loop, every time it crosses from one L-region to another it meets L, so it can only do that twice, so it can only pass through two of the L-regions. And since any two of those earlier loops meet, there must be an L-region they both pass through. I claim that in fact there is a single L-region through which all earlier loops pass. Suppose that's not so, and consider two earlier loops M,N. They meet in, say, region A; perhaps M goes through another region B and perhaps N goes through another region C. Now consider any other loop O. It has to meet either A or B, and it has to meet either A or C. If it doesn't meet A then it must meet both B and C. But this is impossible, because when we do the colouring described earlier B and C have the same colour (whatever colour A isn't), and you therefore can't get from B to C and back to B without crossing L more than twice. So in fact any other loop has to meet region A, and we have found a region through which all loops before L pass. And now we're done, because we can take a loop that goes around the inside boundary of that region very very close to L, which necessarily intersects each earlier loop just twice and L not at all, and then we can perturb it a little to get two intersections with L.
add a comment |
My answer is:
Yes
Assuming that:
Dr Xorile's explanation is correct, however the paper is of finite size and the drawn line is of finite width. If so, then eventually Dr Xorile's method will break down when the parallel loops approach the edge of the paper and/or completely fill the paper. Meaning that one player will not be able to draw anymore lines and therefore lose.
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: "559"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fpuzzling.stackexchange.com%2fquestions%2f76250%2fdrawing-loops-on-a-sheet-of-paper%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
In theory, neither side can win.
This is because
Each player can follow a strategy of drawing a loop that follows parallel and close to the last loop drawn. The last loop goes through each other loop twice, so if you follow it closely enough your line will do so also. Then just make it switch over twice as you're following it around.
add a comment |
In theory, neither side can win.
This is because
Each player can follow a strategy of drawing a loop that follows parallel and close to the last loop drawn. The last loop goes through each other loop twice, so if you follow it closely enough your line will do so also. Then just make it switch over twice as you're following it around.
add a comment |
In theory, neither side can win.
This is because
Each player can follow a strategy of drawing a loop that follows parallel and close to the last loop drawn. The last loop goes through each other loop twice, so if you follow it closely enough your line will do so also. Then just make it switch over twice as you're following it around.
In theory, neither side can win.
This is because
Each player can follow a strategy of drawing a loop that follows parallel and close to the last loop drawn. The last loop goes through each other loop twice, so if you follow it closely enough your line will do so also. Then just make it switch over twice as you're following it around.
answered Dec 10 '18 at 4:11
Dr Xorile
11.5k12364
11.5k12364
add a comment |
add a comment |
When I read this question, I interpreted "loops" more broadly than seems to have been intended, allowing for the possibility that a loop might cross itself. With this possibility in hand, the argument in Dr Xorile's answer no longer works because
if a loop has N self-intersections then a tiny displacement of that loop must cross the original at least 2N times.
In this broader setting, the answer is
still that the game can never finish
and here is one way to see it:
note first of all that any loop divides the plane into regions that can be coloured with two colours, say red and blue, with no two like-coloured regions adjoining. Now take a look at that last loop (call it L) and consider its relations with earlier loops. As you walk around an earlier loop, every time it crosses from one L-region to another it meets L, so it can only do that twice, so it can only pass through two of the L-regions. And since any two of those earlier loops meet, there must be an L-region they both pass through. I claim that in fact there is a single L-region through which all earlier loops pass. Suppose that's not so, and consider two earlier loops M,N. They meet in, say, region A; perhaps M goes through another region B and perhaps N goes through another region C. Now consider any other loop O. It has to meet either A or B, and it has to meet either A or C. If it doesn't meet A then it must meet both B and C. But this is impossible, because when we do the colouring described earlier B and C have the same colour (whatever colour A isn't), and you therefore can't get from B to C and back to B without crossing L more than twice. So in fact any other loop has to meet region A, and we have found a region through which all loops before L pass. And now we're done, because we can take a loop that goes around the inside boundary of that region very very close to L, which necessarily intersects each earlier loop just twice and L not at all, and then we can perturb it a little to get two intersections with L.
add a comment |
When I read this question, I interpreted "loops" more broadly than seems to have been intended, allowing for the possibility that a loop might cross itself. With this possibility in hand, the argument in Dr Xorile's answer no longer works because
if a loop has N self-intersections then a tiny displacement of that loop must cross the original at least 2N times.
In this broader setting, the answer is
still that the game can never finish
and here is one way to see it:
note first of all that any loop divides the plane into regions that can be coloured with two colours, say red and blue, with no two like-coloured regions adjoining. Now take a look at that last loop (call it L) and consider its relations with earlier loops. As you walk around an earlier loop, every time it crosses from one L-region to another it meets L, so it can only do that twice, so it can only pass through two of the L-regions. And since any two of those earlier loops meet, there must be an L-region they both pass through. I claim that in fact there is a single L-region through which all earlier loops pass. Suppose that's not so, and consider two earlier loops M,N. They meet in, say, region A; perhaps M goes through another region B and perhaps N goes through another region C. Now consider any other loop O. It has to meet either A or B, and it has to meet either A or C. If it doesn't meet A then it must meet both B and C. But this is impossible, because when we do the colouring described earlier B and C have the same colour (whatever colour A isn't), and you therefore can't get from B to C and back to B without crossing L more than twice. So in fact any other loop has to meet region A, and we have found a region through which all loops before L pass. And now we're done, because we can take a loop that goes around the inside boundary of that region very very close to L, which necessarily intersects each earlier loop just twice and L not at all, and then we can perturb it a little to get two intersections with L.
add a comment |
When I read this question, I interpreted "loops" more broadly than seems to have been intended, allowing for the possibility that a loop might cross itself. With this possibility in hand, the argument in Dr Xorile's answer no longer works because
if a loop has N self-intersections then a tiny displacement of that loop must cross the original at least 2N times.
In this broader setting, the answer is
still that the game can never finish
and here is one way to see it:
note first of all that any loop divides the plane into regions that can be coloured with two colours, say red and blue, with no two like-coloured regions adjoining. Now take a look at that last loop (call it L) and consider its relations with earlier loops. As you walk around an earlier loop, every time it crosses from one L-region to another it meets L, so it can only do that twice, so it can only pass through two of the L-regions. And since any two of those earlier loops meet, there must be an L-region they both pass through. I claim that in fact there is a single L-region through which all earlier loops pass. Suppose that's not so, and consider two earlier loops M,N. They meet in, say, region A; perhaps M goes through another region B and perhaps N goes through another region C. Now consider any other loop O. It has to meet either A or B, and it has to meet either A or C. If it doesn't meet A then it must meet both B and C. But this is impossible, because when we do the colouring described earlier B and C have the same colour (whatever colour A isn't), and you therefore can't get from B to C and back to B without crossing L more than twice. So in fact any other loop has to meet region A, and we have found a region through which all loops before L pass. And now we're done, because we can take a loop that goes around the inside boundary of that region very very close to L, which necessarily intersects each earlier loop just twice and L not at all, and then we can perturb it a little to get two intersections with L.
When I read this question, I interpreted "loops" more broadly than seems to have been intended, allowing for the possibility that a loop might cross itself. With this possibility in hand, the argument in Dr Xorile's answer no longer works because
if a loop has N self-intersections then a tiny displacement of that loop must cross the original at least 2N times.
In this broader setting, the answer is
still that the game can never finish
and here is one way to see it:
note first of all that any loop divides the plane into regions that can be coloured with two colours, say red and blue, with no two like-coloured regions adjoining. Now take a look at that last loop (call it L) and consider its relations with earlier loops. As you walk around an earlier loop, every time it crosses from one L-region to another it meets L, so it can only do that twice, so it can only pass through two of the L-regions. And since any two of those earlier loops meet, there must be an L-region they both pass through. I claim that in fact there is a single L-region through which all earlier loops pass. Suppose that's not so, and consider two earlier loops M,N. They meet in, say, region A; perhaps M goes through another region B and perhaps N goes through another region C. Now consider any other loop O. It has to meet either A or B, and it has to meet either A or C. If it doesn't meet A then it must meet both B and C. But this is impossible, because when we do the colouring described earlier B and C have the same colour (whatever colour A isn't), and you therefore can't get from B to C and back to B without crossing L more than twice. So in fact any other loop has to meet region A, and we have found a region through which all loops before L pass. And now we're done, because we can take a loop that goes around the inside boundary of that region very very close to L, which necessarily intersects each earlier loop just twice and L not at all, and then we can perturb it a little to get two intersections with L.
answered Dec 10 '18 at 20:05
Gareth McCaughan♦
60.4k3151234
60.4k3151234
add a comment |
add a comment |
My answer is:
Yes
Assuming that:
Dr Xorile's explanation is correct, however the paper is of finite size and the drawn line is of finite width. If so, then eventually Dr Xorile's method will break down when the parallel loops approach the edge of the paper and/or completely fill the paper. Meaning that one player will not be able to draw anymore lines and therefore lose.
add a comment |
My answer is:
Yes
Assuming that:
Dr Xorile's explanation is correct, however the paper is of finite size and the drawn line is of finite width. If so, then eventually Dr Xorile's method will break down when the parallel loops approach the edge of the paper and/or completely fill the paper. Meaning that one player will not be able to draw anymore lines and therefore lose.
add a comment |
My answer is:
Yes
Assuming that:
Dr Xorile's explanation is correct, however the paper is of finite size and the drawn line is of finite width. If so, then eventually Dr Xorile's method will break down when the parallel loops approach the edge of the paper and/or completely fill the paper. Meaning that one player will not be able to draw anymore lines and therefore lose.
My answer is:
Yes
Assuming that:
Dr Xorile's explanation is correct, however the paper is of finite size and the drawn line is of finite width. If so, then eventually Dr Xorile's method will break down when the parallel loops approach the edge of the paper and/or completely fill the paper. Meaning that one player will not be able to draw anymore lines and therefore lose.
answered Dec 10 '18 at 10:10
AHKieran
4,181738
4,181738
add a comment |
add a comment |
Thanks for contributing an answer to Puzzling 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%2fpuzzling.stackexchange.com%2fquestions%2f76250%2fdrawing-loops-on-a-sheet-of-paper%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
Are the loops circles? Or any closed shape?
– Dr Xorile
Dec 10 '18 at 3:14
Any closed shape.
– Stefan
Dec 10 '18 at 3:37