9
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ For $n=3,4$ the second player has a winning strategy. Have you checked any bigger $n$ by hand? $\endgroup$ – Joonas Ilmavirta Mar 9 '15 at 1:26
  • 2
    $\begingroup$ The game is parametrized by $n$, presumably, as in the theorem. $\endgroup$ – Noah Schweber Mar 9 '15 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 Conlon Mar 9 '15 at 5:22
9
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.