MDantas's blog

Hard Game Theory Problem
By MDantas, 10 years ago, In English

Recently (not so recently) I was the problem setter of one SRM. When I was developing the problems I had the idea of creating the following problem:

Given N points on a cartesian plane, two players plays the following game in alternate rounds:

  • The player of each round must choose two points and draw a segment of line between them as long as this segment of line doesn't intersect with any segment created before.

  • The player who can not draw a segment of line anymore loses the game.

  • Given that both players plays optimally, who is the winner?

This problem is almost the same as the Div2Hard from SRM624 ( http://community.topcoder.com/stat?c=problem_statement&pm=13204&rd=15857 ), but now we don't have the restriction that the points must be part of a convex polygon. I've asked lots of amazing coders (including target coders) but no one found a solution yet or proved that this problem is unsolvable in polynomial time.

The best solution I could come up with is the most naive one (O(2^N)). My question here is if it's possible to solve this problem with a better solution or even prove that it's indeed unsolvable.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

yes you can, using the Grundy numbers .

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The convex polygon one can be solved with Grundy Numbers indeed, but I'm afraid it's not possible to do the same when I have random points on a cartesian plane.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No solutions? =/

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If target coders couldn't come up with a efficient solution then do you really expect the other coders to help you? XD

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This game is a special case of Node-Kayles game, so it can be solved in O(1.6052^edges).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sad to see exponential expression :(( that means it is an NP Hard problem?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Node-Kayles is PSPACE-complete, but I'm not sure if it's equivalent to the problem in question

      → Reply