Two players place red and blue stones on a chessboard. The goal is to make a rectangle with all red or all blue corners. Who wins?

83 Views Asked by At

Imagine a game played on a 3-by-7 chessboard. There are two players in this game - one with red stones and one with blue stones. The goal of the game is to make a rectangle with vertices all of your own color. The corners do not need to be connected by solid lines of stones. For example, using chess notation, if a player has red stones on a1, b1, a6, and b6, then they win the game.

Does a winning strategy for either player exist? If it does, what is it? It is known that this game cannot end in a draw - every 2-coloring of a $3\times 7$ lattice grid is guaranteed to contain a rectangle with vertices of the same color.

Additionally, this can be generalized to $n$ players with different colors on an $(n+1)\times (\frac{n^2(n+1)}{2}+1)$ board. Who wins in these variations?

1

There are 1 best solutions below

0
On BEST ANSWER

Nice Question! Zeremelo's Theorem says that in any finite two player perfect information game that cannot end in a draw one of the two players must have a winning strategy. So, yes your statement that there does not exist a draw, implies that one of the two players has a winning strategy.

I believe this game can be thought of as a hypergraph game. Therefore, the argument of strategy stealing implies that Player 1 has the winning strategy.

Unfortunately, Idon't know what the wining strategy is, but Player 1 certainly has it.