Dogfight
Two players play a game on the cartesian plane which occurs in 2 phases. In the first phase, a number n is selected from { 2 , 3 , 4 , … , 9 9 9 } . The first player then places a point at a location ( x , y ) in the plane satisfying − n ≤ x ≤ n , − n ≤ y ≤ n and x , y integers. The players alternate placing points until a total of n points have been placed.
In the second phase, the first player picks two distinct points in the plane that are not joined and joins them by a curve that does not intersect itself, any of the other n − 2 points, or any of the already drawn curves. The players alternate turns, drawing curves in this manner. The first player who is unable to draw a curve loses. For the 998 starting values of n , determine how many of these the first player has a winning strategy for.
Details and assumptions
The players get to choose where they want to place their points.
The curve is a continuous path which does not include the endpoints. Hence, 2 curves may seem to intersect at one of the n points.
The answer is 500.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
Let me add a comment to answer the CM's question to Michal F, and which needs answering in my first post.
Suppose that there was a face with four or more sides such that it was not possible to draw a chord across it without violating the simplicity of the graph. If we considered any four a , b , c , d of the vertices of that face, this would mean that every pair of those four vertices was already connected in the graph. Just consider those four vertices and their six connecting lines. If we added a fifth vertex e inside the face, and joined that vertex to each of the four vertices a , b , c , d (this is possible, since all these new lines can lie inside the face) then the vertices a , b , c , d , e and the ten lines mentioned form a planar representation of the complete graph K 5 with 5 vertices. But this graph is known to be nonplanar. QED.
Basically have a look at the theorem at the last page of this pdf for a proof of what I'm going to state.
If a maximal planar graph has v vertices with v > 2 , then it has precisely 3 v − 6 edges.
It's clear that the first player wins every time that the number of edges is odd. It is easy to see that this happens when n = 2 or when n is odd.
The number of odd numbers in the set is 2 9 9 9 + 1 − 1 = 4 9 9
Therefore the answer is 5 0 0
q.e.d.
P.S. The first phase does not affect the outcome of game!
For n = 2 the first player makes the only possible move and wins. Below we assume that n ≥ 3 .
The state of the game at any moment is a planar graph on n vertices. As long as the planar graph contains at least two components, or contains a face that is not a triangle, there is an available move: connect two components, or draw a new edge that divides a face into two smaller ones. (Note that the part about the players alternately choosing the n points as grid points in some range is a red herring. Everything in this proof works for any set of n distinct points in the plane.)
Thus, the game ends when the players reach a plane triangulation: a connected simple planar graph in which all faces are triangles. From Euler's formula for planar graphs we can easily deduce that each plane triangulation on n ≥ 3 vertices has exactly 3 n − 6 edges. Thus for any fixed n the outcome of the game does not depend on the players' actions. Player 1 wins iff 3 n − 6 is odd.
From the positions we were asked to examine, the winning positions for player 1 are { 2 } ∪ { 3 , 5 , 7 , … , 9 9 9 } . Thus there are exactly 5 0 0 of them.
Moderator note:
When we have a face that is not a triangle, why are we always able to draw an edge in it? We are not allowed to join two vertices that are already joined by an edge, so how do we know that we will not violate this condition?
Label adjacent vertices A , B , C , D on a face that's not a triangle. If A is not connected to C we can join them. However if A is connected to C outside the face, then there cannot be any other lines leaving B because that line would have to cross the triangle A B C outside the face. So we can connect B to D inside the face.
Log in to reply
Well almost. If A were connected to C outside the face, then the edges A B , B C , C A would form a triangle, and D would belong to either the bounded or the unbounded region defined by that triangle. The vertex B could connect to other points in the graph; what is at issue is whether/how it connects to D . Any line joining B to D must lie wholly inside the same region (unbounded or bounded) defined by the triangle as D . For either type of region, this line must run through the face. Thus B and D cannot be connected to each other outside the face. Thus either A and C , or else B and D , can always be connected inside the face.
Your argument is the meat of the proof that K 5 is nonplanar.
Log in to reply
Right. A and C could be connected by going 'behind' D , but in that case D couldn't connect to B . (basically BD and AC can't both connect outside the face).
It's not quite true that each plane triangulation on n vertices has 3 n − 6 edges. Counterexample: if you arrange 4 points in a square, then any triangulation has 5 edges, whereas if you arrange them where 1 point is inside the triangle formed by the other 3, any triangulation has 6 edges. In general, the number of edges in the complete triangulation is a function of the number n of vertices and the number h of vertices that lie on the convex hull of all the vertices.
Log in to reply
You are mistaken. If you arrange them in a square ABCD and draw your five edges (the sides of the square and one diagonal: say, AC), you still have one face with 4 vertices: the outer face. You can still draw one more curve (note: curve, not a straight line, the statement talks about arbitrary curves!) that goes outside the square and connects the other two points (BD in our case). This curve is the sixth edge of the plane triangulation you are missing.
Log in to reply
Oh, whoops, you're right; I missed that the curves didn't have to be lines (luckily, I don't think it actually changes the final answer, since except for n = 2 the last player to place a point can control the parity of the number of edges in a normal polygonal triangulation).
There are n points chosen in the first phase, hence n C 2 lines can be drawn between them. For the first player to be able to draw the last line (which is the primary condition for winning) , it is obvious that the no. of lines must be odd , which is fulfilled if n=2 or any other odd no. As, n is an integer varying from 2 up to 999 , so there are 5 0 0 starting values of n, for the first player to have a winning strategy.
Those lines can't all be drawn though as some would cross over each other.
Log in to reply
The drawn "curves" (mentioned in my post as lines) need not be straight. They may be drawn as per the wish of the player, the only criterion is that, they must join two of the points selected in the first phase. So, if a player plays optimally, he would be careful enough to draw a curve avoiding intersections (or cross-overs), unless all the points are used up, and above all, he could utilize the space outside the n ∗ n space to draw the curves.
Log in to reply
They have to lie in the plane though. For example with n=5, you say we can draw 10 curves, however it is actually only possible to draw 9 (try it).
Log in to reply
@Matt McNabb – And even if it were possible to draw all n C 2 lines, n C 2 is not odd when n = 2 or n is odd. For example 5 C 2 = 1 0 . In fact, n C 2 is odd when n is congruent to either 2 or 3 modulo 4 .
Since the joining curves can be any shape, the original positioning of the points is irrelevant. The game will produce a maximal planar (simple) graph with n vertices.
If n = 2 , then Player 1 wins by drawing the only possible line.
If n ≥ 3 , then any maximal planar graph with n vertices has 3 n − 6 edges. To see this, note that a maximal planar graph must be connected (otherwise a line could be drawn joining a pair of components) and each face of the graph must be a triangle (if there were a face with more than three vertices, a chord could be drawn within that face). Thus 3 f = 2 e , and so Euler's formula gives 3 n − e = 6 .
If n ≥ 3 is even, any maximal planar graph has an even number of edges, and so Player 2 will draw the last line, and hence win. If n ≥ 3 is odd, any maximal planar graph has an odd number of edges, and so Player 1 will draw the last line, and hence win.
Thus, irrespective of any strategy, Player 1 will win if either n = 2 or n ≥ 3 is odd, and Player 2 will win if n ≥ 3 is even. Thus there are 5 0 0 values of n for which Player 1 will win.