Skip to main content
added 27 characters in body
Source Link
gowers
  • 29k
  • 29
  • 145
  • 182

A better approach

Here's another idea. Suppose we have a board of width 4m. Consider the transformation that adds 2m to the x and y coordinates, mod 4m. This takes horizontal lines to horizontal lines and vertical lines to vertical lines. It also takes diagonals to diagonals and is self-inverse. Unfortunately, the two diagonals are still invariant.

Here's another idea. Suppose we have a board of width 4m. Consider the transformation that adds 2m to the x and y coordinates, mod 4m. This takes horizontal lines to horizontal lines and vertical lines to vertical lines. It also takes diagonals to diagonals and is self-inverse. Unfortunately, the two diagonals are still invariant.

A better approach

Here's another idea. Suppose we have a board of width 4m. Consider the transformation that adds 2m to the x and y coordinates, mod 4m. This takes horizontal lines to horizontal lines and vertical lines to vertical lines. It also takes diagonals to diagonals and is self-inverse. Unfortunately, the two diagonals are still invariant.

added 451 characters in body
Source Link
gowers
  • 29k
  • 29
  • 145
  • 182

Extra remark: the transformation I define above can be described as follows. Take the left half and right half of the board and reflect each one about a vertical line through its centre. Then translate the whole board vertically by 2m (mod 4m). The result is to send all vertical/horizontal lines to different vertical/horizontal lines and to interchange the two diagonals. It's easy to see that doing this transformation twice gives the identity.

Extra remark: the transformation I define above can be described as follows. Take the left half and right half of the board and reflect each one about a vertical line through its centre. Then translate the whole board vertically by 2m (mod 4m). The result is to send all vertical/horizontal lines to different vertical/horizontal lines and to interchange the two diagonals. It's easy to see that doing this transformation twice gives the identity.

Source Link
gowers
  • 29k
  • 29
  • 145
  • 182

OK, let's first consider an even board and a straightforward strategy steal where the second player rotates the first player's moves by 180 degrees about the centre of the board. This works fine for horizontal and vertical lines, since if the second player completes such a line then the first player must have completed the 180-degree rotation of that line in the previous move. However, it runs into problems with diagonals.

The problem is that if you rotate a diagonal through 180 degrees you get the same diagonal, so the above proof that the strategy works breaks down.

What can we do about this? One idea is to try a slightly more complicated strategy steal. We'd like to choose a transformation that takes lines to lines such that no line is invariant. All the obvious transformations of order 2 -- reflections and half turns -- have invariant lines. So we could try a rotation through 90 degrees. Unfortunately, this doesn't work, since, denoting this rotation by R, if the first player plays point x and then point R^{-1}x, player 2 cannot play R(R^{-1}(x)).

But we could at least partition all the points on the board into quadruples of the form {x,Rx,R^2x,R^3x} and try to use this partition. What happens if the second player plays Rx if possible and R^{-1}x if it is not possible to play Rx? (It is easy to check that this strategy can be implemented.)

A simple lemma is that whenever player 2 plays a point y, R^{-1}y is already on the board. Here is the proof. If player 2 plays y, then either player 1 has just played R^{-1}y, or player 1 has just played Ry and the point R^2y was already played. Now if the point R^2y was already played, then either it was played by player 1, in which case player 2 would have played R^3y (unless it was already played, but that's fine too and is probably not possible -- no need to check), or it was played by player 2, which again could only have happened if player 1 had played R^3y.

Let me try again with a much nicer proof. How do quadruples of the form {x,Rx,R^2x,R^3x} fill up? Without loss of generality the first point to be filled is x. Then the next point has to be Rx. After that, when player 2 next plays a point in the quadruple all four points are played. Done.

Therefore, if player 2 completes a line ... damn, this doesn't work.

Let me end by showing that that whole strategy fails, since even though it doesn't answer the question it provides some evidence that strategy stealing isn't going to work. If player 1 knows that player 2 is going to adopt the 90-degree strategy steal, then player 1 can fill up the top row, starting from the left. Then player 2 will fill the rightmost column, starting from the top. This continues until player 1 is blocked by the top right corner. Player 1 then fills the bottom left corner and player 2 completes a line.

Obviously, it's not surprising that it failed, since it was a fairly unlikely idea in the first place.

Here's another idea. Suppose we have a board of width 4m. Consider the transformation that adds 2m to the x and y coordinates, mod 4m. This takes horizontal lines to horizontal lines and vertical lines to vertical lines. It also takes diagonals to diagonals and is self-inverse. Unfortunately, the two diagonals are still invariant.

We can remedy that last problem by reflecting in a vertical line through the centre of the board. And if I am not much mistaken, the result is a new transformation that is still self-inverse, takes lines to lines, and has no invariant lines. (For that last property I needed the width to be a multiple of 4.)

So we can do it by strategy stealing after all, at least in this case.