Results 1 to 3 of 3

Thread: The connected Game

  1. #1
    Newbie
    Joined
    Apr 2015
    From
    Singapore
    Posts
    6

    The connected Game

    There are n dots which are on a plane (flat surface). There are two players, A and B, who move alternatively; A moves first. The rules of the game are the same for both players: at each move they can connect two points, but they cannot connect points which were already directly connected to each other or connect a point with itself.

    To put it simply, they build a graph (with predefined n vertices) by connecting some of the dots. The winner is the one who makes the graph connected (a graph is connected if there is a path between any two nodes of the graph, however, not every two nodes have to be connected directly). What is the winning strategy for player A, if such exists



    SOME OF HELPFUL HINTS

    • Clearly, if n = 2, the first player always wins.

    •If n = 3, the second player always wins.

    •If n = 4, the first player has a winning strategy.

    •What if n =14?

    • I suggest you find yourselves a partner its way more fun (unless you like playing with yourself) and play several games where n = 14. Determine which player (first or second) has a winning strategy? Provide convincing argument.

    •Try then the general case (more involving)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    1,061
    Thanks
    410

    Re: The connected Game

    What comes to mind is this: A play loses on their turn iff they face two complete graphs (including a complete graph on one vertex). Thus the outcome is determined once the points have been connected into exactly two connected graphs (including an isolated vertex as counting as connected). The win/loss at that point will be 100% determined by the odd/even parity of the number of edges required to complete those two graphs. So your winning move is if you can connect three disjoint connected graphs, so as to make it into two disjoint connected graphs with an odd number of edges left to complete those two graphs. That's the condition that you want to find, but never can allow your opponent to find.
    If you have 3 connected graphs, with number of verts a, b, c, and a total of k edges, and it's your move, can you win?
    If move to connect the a & b graphs, then your opponent faces: (k+1) edges inside 2 connected graphs. Since that will fill out to [ (a+b) choose 2 ] + [ c choose 2 ] edges before someone is forced to lose, your opponent wins if [ (a+b) choose 2 ] + [ c choose 2 ] - (k+1) is odd, and your opponent loses if it's even.
    Let f(n) = 0 if n congruent to 0 or 1 mod 4, and f(n) = 1 in the 2, 3 mod 4 case.
    Then can show that parity[ n choose 2 ] = parity (f(n)).
    So you win if you face 3 disjoint connected graphs, with total k edges and verticies counts a, b, and c, such that:
    parity[ f(a+b) ] + parity[ f(c) ] - parity[k+1] = even, so if parity[ f(a+b) ] + parity[ f(c) ] + parity[k] = odd, so if parity[ f(a+b) ] + parity[ f(c) ] = opposite parity of k.
    Then the question becomes, given a, b, c and a choosen parity, can you choose two of them so that that works? Not always.
    Ex: If a=b=c mod 4, then no matter how you poermute a, b, and c, you end up with the condition parity[ f(2a) ] + parity[ f(a) ] = opposite parity of k.
    If a=b=c=0 mod 4, then parity[ f(2a) ] + parity[ f(a) ] = even + even = even, so you're only able to make the winning move in that case if k were odd (if you'd gone 2nd).
    If a=b=c=1 mod 4, then parity[ f(2a) ] + parity[ f(a) ] = odd + even = odd, so you're only able to make the winning move in that case if k were even (if you'd gone 1st).
    If a=b=c=2 mod 4, then parity[ f(2a) ] + parity[ f(a) ] = even + odd = odd, so you're only able to make the winning move in that case if k were even (if you'd gone 1st).
    If a=b=c=3 mod 4, then parity[ f(2a) ] + parity[ f(a) ] = odd + odd = even, so you're only able to make the winning move in that case if k were odd (if you'd gone 2nd).
    Also, note that as soon as there are a total of 3 connected graphs with vert numbers a, b, and c, and total edges k, then if you don't have a winning move, then after your move, it's still the same situation, excpet for k+1 edges. Since you did NOT have a winning move, it must be the case that parity[ f(a+b) ] + parity[ f(c) ] = same parity as k.
    Therefore, after you move, your opponent sees a {a, b, c; k+1} situation, and it's true that parity[ f(a+b) ] + parity[ f(c) ] = same parity as k = opposite parity as (k+1), and so your opponent wins.

    This shows that the moment those n verticies have been connected up into exactly 3 disjoint connected graphs (including singletons as such), the winner is determined (assuming everyone plays correctly), and that winner is based only on the following data: the number of vertices of those 3 graphs, taken only mod 4, and the parity of the the number of edges placed. And obviously, from a player's point of view, when their turn comes up, the parity of the the number of edges placed will be solely determined by whether that player had gone 1st or 2nd.

    So now the game is about deciding how to drive the initial setup into the situation I just described. That's starting to look like more thinking than I care to invest without a bunch of writing, so I'm going to stop with the details there. I'll make notation of state {a1, a2, ..., as; k} meaning it's broken into s connected graphs with vertcies count a1, a2, ... as respectively, and k edges.
    It's certain that the game is decided at {a1, a2, a3; k} based only on the mod 4 values a1, a2, a3 and the parity of k.
    A player looking at {a1, a2, a3, a4; k} gets to choose whether to send it to {a1, a2, a3, a4; k+1}, or (WLOG) {a1, a2, (a3+a4); k+1}, UNLESS all 4 graphs are already complete! (A single isolated vertex counts as complete.)
    If there is NO permutation like {a1, a2, (a3+a4); k+1} that wins for that player, and not all 4 graphs are complete, then the next player, facing {a1, a2, a3, a4; k+1} will be able to find a permutation {a1, a2, (a3+a4); k+2} that wins (since those a's won't have changed, but the parity of the number of edges will have).
    This shows that the moment there are exactly 4 connected components, the game is decided, based on the mod 4 values of their numbers of verticies, and the parity of the number of edges placed (i.e.
    which player went first).
    The same reasoning seems to continue, so that as soon as 5 connected components, it's decided, and so forth.
    It seems to me that the thing that keeps this from being a simple pattern is that isolated vertices count as complete graphs, and a move connecting isolated vertices forms a new complete graph. Graphs being complete change the options, and so make it more complicated.

    I'll make one more generic comment:
    Fix n >= 4, the first player is always looking at the same situation on his/her first move - but that's also true for the 2nd player. It's the 2nd player who gets the first actual "choice" - whether to place an edge so that the two edges share or don't share a vertex. So in effect, the 2nd player gets to decide whether the 1st player "starts" (it's actually the 1st player's second move) by looking at:
    \left( \amalg_{1}^{n-3} K_{1} \right) \amalg \left( K_{3} - \{e\} \right)
    or
    \left( \amalg_{1}^{n-4} K_{1} \right) \amalg \left( K_{2} \right) \amalg \left( K_{2} \right).

    That's all I care to invest for now. Maybe I'll think about it more tomorrow.
    Last edited by johnsomeone; Jun 4th 2015 at 02:43 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,692
    Thanks
    544

    Re: The connected Game

    I don't understand the claim that the first player has a winning strategy: it just seems to me that the first player always wins with an even number of points and the second player wins with an odd number of points. The proof is by induction because we can replace a set of connected nodes by a single node to get a smaller case.

    Edit: I've seen the point I was missing now.
    Last edited by Archie; Jun 4th 2015 at 03:20 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What is a simply connected and 4-connected graph?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 11th 2012, 11:18 AM
  2. Every path-connected metric space is connected
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Sep 13th 2011, 07:31 AM
  3. Proof that union of two connected non disjoint sets is connected
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Sep 27th 2009, 09:22 AM
  4. Replies: 1
    Last Post: Apr 18th 2008, 08:19 AM
  5. Replies: 5
    Last Post: Apr 7th 2007, 10:52 AM

Search Tags


/mathhelpforum @mathhelpforum