Skip to main content
1 of 3
joro
  • 25.4k
  • 10
  • 66
  • 121

Game on a square grid (part II)

Related to this question, where there the solution was unexpected for us.

Let $n,m$ be positive integers, $n \le m \le n^2/2$.

The board is $n \times n$ square grid.

  • Two players, $A,B$ make $m$ moves, where at each move each of them color uncolored vertex of the grid red.

  • $A,B$ take moves in turns.

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

  • If the line intersects another line or passes through a third red 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.

  • If there are no valid moves, the game is draw.

Is there winning strategy depending on $n,m$?

If the general solution is hard fix $m$, say let $m=\lfloor \frac{n^2}{4} \rfloor$

joro
  • 25.4k
  • 10
  • 66
  • 121