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.