Skip to main content
3 of 3
clarified about two phases
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.

Phase 1:

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

Phase 2:

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

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