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 '18 at 13:39
  • 1
    $\begingroup$ @giannispapav Yes. $\endgroup$ – Preechapak Tekasuk Aug 16 '18 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 '18 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 '18 at 13:43
  • $\begingroup$ Then Bob can easily force a win. $\endgroup$ – Servaes Aug 16 '18 at 13:43
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$
17
  • 1
    $\begingroup$ What if Alice plays something on the right hand edge of the grid? $\endgroup$ – Jack M Aug 16 '18 at 13:48
  • 1
    $\begingroup$ @JackM The $+2$ is mod 4. $\endgroup$ – Mike Earnest Aug 16 '18 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 '18 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 '18 at 14:17
  • 1
    $\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 '18 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 '18 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.