20
$\begingroup$

Alice and Bob are playing the following game: They have a 4x4 empty grid and take turns coloring one square each, starting with Alice, both using the same color. Whoever completes any 2x2 area on the grid (after having made his move) is the loser. Is there any winning strategy for any of the two players?

I have played the game several times and can't see a clear strategy for any of the two. It seems to me that Bob will loose.

Any ideas?

$\endgroup$
7
  • 5
    $\begingroup$ @Preechapak Tekasuk are A and B using the same colour? $\endgroup$
    – 1123581321
    Aug 16, 2018 at 13:39
  • 1
    $\begingroup$ @giannispapav Yes. $\endgroup$
    – Preechapak Tekasuk
    Aug 16, 2018 at 13:41
  • $\begingroup$ @PreechapakTekasuk You should make this clear in the question. I interpreted it the same way that Ronald Blake did, that they were using different colors. $\endgroup$
    – saulspatz
    Aug 16, 2018 at 13:42
  • $\begingroup$ There is a winning strategy. There's no possible draw, so it must be unfair. See Wolfram for unfair games. $\endgroup$
    – stretch
    Aug 16, 2018 at 13:43
  • $\begingroup$ Then Bob can easily force a win. $\endgroup$
    – Servaes
    Aug 16, 2018 at 13:43

2 Answers 2

Reset to default
20
$\begingroup$

If Alice selects a square $(i,j)$, Bob should choose $(i+2,j)$. In this way he will never complete a square before Alice does, and hence Bob will always win. Of course, modulo 4 is required with this strategy.

Likewise a strategy $(i,j+2)$ would have worked. Note that these strategies are always possible, because they fill the full grid with particular pairs.

In the case of a $n \times n$ grid for odd values of $n=2 m + 1$, there is a winning strategy for Alice. If she starts with $(m,m)$ as the first square and responds to any choice $(i,j)$ of Bob by playing $(2 m -i,2 m-j)$, Bob will make the first $2\times2$ square. This approach can also be generalised to rectangular grids, and will result in a winning strategy for Alice when both dimensions are odd.

Thanks to @Philip for pointing out that the pairing $(i,j)$ and $(i+2,j+2)$ would not work in the $4\times4$ grid, because the choosing of the 4 corners by Alice would create a central square made by Bob.

Thanks to @Carmeister for pointing out that a generalisation for even values $n=2m$ by pairing the square $(i,j)$ of Alice by Bob taking $(i+m,j)$, would also not be successful for the same reason. By choosing suitable squares (this time not the corners) Alice could force Bob to make a central square as well if he would stick to this particular strategy.

So the question of the existence/absence of a winning strategy for even sided square grids larger than $4\times4$ is still open.

$\endgroup$
19
  • 1
    $\begingroup$ What if Alice plays something on the right hand edge of the grid? $\endgroup$
    – Jack M
    Aug 16, 2018 at 13:48
  • 1
    $\begingroup$ @JackM The $+2$ is mod 4. $\endgroup$
    – Mike Earnest
    Aug 16, 2018 at 13:48
  • 1
    $\begingroup$ Note that this works because the element $(2, 0)$ is of order two in the group $\mathbb Z/2\mathbb Z\times\mathbb Z/2\mathbb Z$, which implies that Bob never risks having to play on a square Alice already played on. On say, a $5\times 5$ grid, I'm not sure how to generalize this. $\endgroup$
    – Jack M
    Aug 16, 2018 at 13:58
  • 4
    $\begingroup$ For odd $n$, Alice seems to have a winning strategy. She starts by coloring the center square and then mirrors Bob's moves thereafter. $\endgroup$
    – Jens
    Aug 16, 2018 at 14:17
  • 2
    $\begingroup$ @Jens Again, this generalizes to rectangular grids, so it appears that the problem is solved for all rectangular grids. Alice wins if both dimensions are odd, and Bob wins otherwise. $\endgroup$
    – saulspatz
    Aug 16, 2018 at 14:36
0
$\begingroup$

The way I see it Alice wins the first time. Because the 'one square' she colours can be any size 2by 2, 3by 3 or 4by 4, she doesn't get a 2nd chance to colour.

$\endgroup$
1
  • 2
    $\begingroup$ Whoever completes a 2x2 square is the loser so even if Alice were permitted to colour a 2x2 square (or larger) she wouldn't. I think you have not interpreted the question correctly. $\endgroup$
    – James K
    Aug 16, 2018 at 18:41

You must log in to answer this question.

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