5
$\begingroup$

Not research level, comments are welcome.

Consider the following game:

  • The board is the vertices of an $n$ by $n$ square grid.

  • Two players take moves in turns.

  • A move is picking two vertices and drawing a straight line between them.

  • If the line intersects another line or passes through a third vertex, the game ends and the player who made the move loses the game. Two or more lines are allowed to end at the same vertex.

Is there winning strategy depending on $n$?

Partial result:

We believe if we take the board to be the vertices of regular polygon, the first player always wins, even if they don't have any skills except finding a non-losing move if it exists.

Improve this question
$\endgroup$
3
  • $\begingroup$ On a hexagon, the first player can win, but the strategy is non-trivial as they must make sure an odd number of interior edges will be drawn. If the second player manages to draw lines from 1 to 3 and from 4 to 6, they'll win instead. $\endgroup$
    – Glorfindel
    Commented May 5, 2020 at 12:12
  • $\begingroup$ @Glorfindel Confusion is possible, but we believe in a $n$ regular polygon there are $n-3$ non-intersecting diagonals and $n$ sides. $\endgroup$
    – joro
    Commented May 5, 2020 at 12:43
  • $\begingroup$ Ah, I missed a long diagonal from 1 to 4 (or 3 to 6) is still possible in this case. However, for higher $n$ it still might be non-trivial. $\endgroup$
    – Glorfindel
    Commented May 5, 2020 at 12:51

1 Answer 1

Reset to default
11
$\begingroup$

Doesn't a symmetry argument make this question rather simple?

If $n$ is odd, the second player (blue) can always mirror the first player's (red) moves (reflected through, or rotated by $\pi$ radians around the origin of the grid, i.e. its center vertex), so the first player loses.

enter image description here

If $n$ is even, the first player can draw one of the diagonals of the central square (orange; this move can't be mirrored) and can then mirror all of the second player's moves, so the second player loses.

enter image description here

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Many thanks! Are there boards for which this game is hard? This is not rigorous, but what if the board is random $n$ points in the plane? $\endgroup$
    – joro
    Commented May 5, 2020 at 11:58
  • $\begingroup$ Perhaps it depends on the number of edges and of possible edge crossings? (Note that unlike the square grid, you can draw a line between all points if they're randomly distributed; the square grid excludes some because there's another vertex in the middle.) $\endgroup$
    – Glorfindel
    Commented May 5, 2020 at 12:14
  • $\begingroup$ your "reflection through the origin" is actually rotation by $\pi$ radians, right? So your argument would work for any board which is preserved by such a rotation. $\endgroup$
    – Nick Gill
    Commented May 5, 2020 at 13:03
  • $\begingroup$ @NickGill that's correct. $\endgroup$
    – Glorfindel
    Commented May 5, 2020 at 13:07
  • $\begingroup$ For 3 by 3 or larger odd board do you have a game where the first player wins when the second player plays weak, but doesn't make obviously bad moves? We have conjecture that this impossible. $\endgroup$
    – joro
    Commented May 5, 2020 at 15:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .