Given $n$. Two players in turn mark points on the plane. No three may be collinear, no $n$ may form a convex $n$-gon. The player who does not have legal move loses. Who has a winning strategy?
$\begingroup$
$\endgroup$
3
asked Mar 9, 2015 at 1:15
-
1$\begingroup$ For $n=3,4$ the second player has a winning strategy. Have you checked any bigger $n$ by hand? $\endgroup$– Joonas IlmavirtaMar 9, 2015 at 1:26
-
2$\begingroup$ The game is parametrized by $n$, presumably, as in the theorem. $\endgroup$– Noah SchweberMar 9, 2015 at 1:56
-
2$\begingroup$ Unless there is a generic argument like strategy stealing (which doesn't work in this case), this is likely to be a difficult question. It might be more fruitful to consider how long the game lasts. The Erdős-Szekeres theorem gives some bound but it might be possible to improve it. $\endgroup$– David ConlonMar 9, 2015 at 5:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The problem was raised and discussed in Parikshit Kolipaka and Sathish Govindarajan, Two player game variant of the Erdős-Szekeres problem, Discrete Math. Theor. Comput. Sci. 15 (2013), no. 3, 73–100, MR3141828. It says the second player wins for $n=5$.
answered Mar 9, 2015 at 1:56