4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are the loops circles? Or any closed shape? $\endgroup$ – Dr Xorile Dec 10 '18 at 3:14
  • $\begingroup$ Any closed shape. $\endgroup$ – Stefan Dec 10 '18 at 3:37
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.