### MDantas's blog

By MDantas, 6 years ago, , 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. hard, Comments (7)
 » 6 years ago, # | ← Rev. 2 →   yes you can, using the Grundy numbers .
•  » » 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.
 » No solutions? =/
•  » » If target coders couldn't come up with a efficient solution then do you really expect the other coders to help you? XD
 » This game is a special case of Node-Kayles game, so it can be solved in O(1.6052^edges).
•  » » Sad to see exponential expression :(( that means it is an NP Hard problem?
•  » » » Node-Kayles is PSPACE-complete, but I'm not sure if it's equivalent to the problem in question