3 Mistake in proof (odd <-> even)

Updated for the 4m+2 x 4m+2 case

At the risk of stating the obvious, the strategies described here for the 3x3 and 4n x 4n games can be described by simple pairings. For instance, the 4x4 pairing is:

a b c d
e f g h
b a d c
f e h g

Whatever move P1 makes, P2 makes the move with the same letter.

The 3x3 pairing is:

a b c
c * d
d a b

P1 plays in the central point *, and then follows the same rule as P2 in the 4x4 game.

When does such a pairing lead to a winning strategy? We require that whenever a line is formed by playing the pairing of a point on the grid, there must already be a line on the grid somewhere (so that the other player has already lost). The pairing must satisfy the following condition:

Let L be any line in the grid (row, column, or diagonal). Mark all the points of L with an X, and mark all the pairings of those points too. If n is odd, mark the central point * (P1's first move). Then for each point in L (that is not the central point *), if we erase it from the grid, the grid must still contain a line of X's.

This is always true if L's pairings form another line, disjoint from L; such is the case with the 4n x 4n pairings resulting from gowers' Better Approach. But it is also true for the 3x3 pairing given above, as you can check for yourselves fairly easily.

But there is no such pairing on the 5x5 board! This is rather messy, so I might skim over some details. Feel free to ask for clarification. Here the 'map' of a line L is the set of pairings of the points in L; the central point * is considered as being paired with itself.

Claim 1: No line L can contain both a point and its pairing. For then there would only be at most three paired points outside L, together with the central point *; and these four points can't be enough to form a line whenever a point of L is erased.

Claim 2: Any line L going through the central point * must map to a line that also goes through . For the pairs of the four non- points in L would otherwise not be enough to form a line whenever a non-* point of L is erased. Thus, if we call the union of Row 3, Column 3, and the two diagonals the asterisk-set, then points in (resp. outside) the asterisk-set must pair with points in (resp. outside) the asterisk set.

Claim 3: Any line L not going through * must map to a disjoint (and therefore parallel) line. For there are at most 6 X's outside the line; if four of these form a line K, intersecting L at point p, say, then erasing point p will leave the grid without a line (because the two remaining points, together with at most one point from L and one point from K, are not enough to form a line).

Claim 4: Any line L not going through * must map to a disjoint parallel line not going through *. For Claim 2 tells us that lines going through * map to lines going through *, and the pairing function is its own inverse.

Now, consider Row 1 and the row that it maps to under the pairing: Row r, say. The vertical bisector of the grid (Column 3) intersects these rows at points p1 and pr, say. Points on Row 1 not equal to p1 pair with points on Row r not equal to pr; so p1 must map to pr. This contradicts Claim 1. So there can be no such pairing. QED

This proof works for any odd n >= 5. It doesn't work for n=3, because Claim 3 fails: the two remaining points, together with at most one point from L and one point from K, are indeed enough to form a line.

Well, but one player has to have a winning strategy! Which one? We can answer this fairly easily for n=5, by brute force computer search, working backwards from the filled board by flagging all positions as winning or losing. There are only $2^25$ positions to consider, and the search takes about 30 seconds on my laptop. It turns out that the 5x5 board is a win for P1, who can make any initial move. (By contrast, in the 3x3 board the only winning move is the central point *.) This tells us two things: (i) P1 wins; (ii) the winning strategy is not a simple pairing.

Update The n x n case, with n = 4m + 2

There is no simple pairing strategy in this case, either. The analysis is simpler for even-numbered grid sizes. We just need:

Claim 1: No line L can contain both a point and its pairing. For then there would only be at most n-2 paired points outside L; and these points can't be enough to form a line whenever a point of L is erased.

Claim 2: Every line L must map to a disjoint line. For there are at most n paired X's outside the line; if n-1 of these form a line K, intersecting L at point p, say, then erasing point p will leave the grid without a line (because the one remaining points, together with at most one point from L and one point from K, are not enough to form a line).

This means that rows map to rows, columns map to columns, and the two diagonals map to each other.

Now, consider the point (a,a) on the leading diagonal. Suppose Row a maps to Row b, and Column a maps to Column c. Then the point (a,a) must be paired with the point (b,c), and this point (b,c) must be on the trailing diagonal: b+c = n+1. So Column a maps to Column c = n+1-b. Thus we have the following implication:

Row a maps to Row b => Column a maps to Column n+1-b

We can interchange rows and columns in this implication, so that

Column n+1-b maps to Column a => Row n+1-b maps to Row n+1-a

Combining these:

Row a maps to Row b => Row n+1-b maps to Row n+1-a

Now, a can't be equal to n+1-a, because n is oddeven. And if a is equal to n+1-b, then Column a maps to Column a, which is not allowed. So we can partition the n rows into groups of the form (a, b, n+1-b, n+1-a). But this is clearly impossible if n is not a multiple of 4. QED

Updated for the 4m+2 x 4m+2 case

Well, but one player has to have a winning strategy! Which one? We can answer this fairly easily for n=5, by brute force computer search, working backwards from the filled board by flagging all positions as winning or losing. There are only 2^25 $2^25$ positions to consider, and the search takes about 30 seconds on my laptop. It turns out that the 5x5 board is a win for P1, who can make any initial move. (By contrast, in the 3x3 board the only winning move is the central point *.) This tells us two things: (i) P1 wins; (ii) the winning strategy is not a simple pairing.

Next stop

Update The n x n case, with n = 4m + 2

There is no simple pairing strategy in this case, either. The analysis is simpler for even-numbered grid sizes. We just need:6x6

Claim 1: No line L can contain both a point and its pairing. For then there would only be at most n-2 paired points outside L; and these points can't be enough to form a line whenever a point of L is erased.

Claim 2: Every line L must map to a disjoint line. For there are at most n paired X's outside the line; if n-1 of these form a line K, intersecting L at point p, say, then erasing point p will leave the grid without a line (because the one remaining points, together with at most one point from L and one point from K, are not enough to form a line).

This may take means that rows map to rows, columns map to columns, and the two diagonals map to each other.

Now, consider the point (a,a) on the leading diagonal. Suppose Row a whilemaps to Row b, and Column a maps to Column c. Then the point (a,a) must be paired with the point (b,c), and this point (b,c) must be on the trailing diagonal: b+c = n+1. So Column a maps to Column c = n+1-b. Thus we have the following implication:

Row a maps to Row b => Column a maps to Column n+1-b

We can interchange rows and columns in this implication, so that

Column n+1-b maps to Column a => Row n+1-b maps to Row n+1-a

Combining these:

Row a maps to Row b => Row n+1-b maps to Row n+1-a

Now, a can't be equal to n+1-a, because n is odd. And if a is equal to n+1-b, then Column a maps to Column a, which is not allowed. So we can partition the n rows into groups of the form (a, b, n+1-b, n+1-a). But this is clearly impossible if n is not a multiple of 4. QED

1

At the risk of stating the obvious, the strategies described here for the 3x3 and 4n x 4n games can be described by simple pairings. For instance, the 4x4 pairing is:

a b c d
e f g h
b a d c
f e h g

Whatever move P1 makes, P2 makes the move with the same letter.

The 3x3 pairing is:

a b c
c * d
d a b

P1 plays in the central point *, and then follows the same rule as P2 in the 4x4 game.

When does such a pairing lead to a winning strategy? We require that whenever a line is formed by playing the pairing of a point on the grid, there must already be a line on the grid somewhere (so that the other player has already lost). The pairing must satisfy the following condition:

Let L be any line in the grid (row, column, or diagonal). Mark all the points of L with an X, and mark all the pairings of those points too. If n is odd, mark the central point * (P1's first move). Then for each point in L (that is not the central point *), if we erase it from the grid, the grid must still contain a line of X's.

This is always true if L's pairings form another line, disjoint from L; such is the case with the 4n x 4n pairings resulting from gowers' Better Approach. But it is also true for the 3x3 pairing given above, as you can check for yourselves fairly easily.

But there is no such pairing on the 5x5 board! This is rather messy, so I might skim over some details. Feel free to ask for clarification. Here the 'map' of a line L is the set of pairings of the points in L; the central point * is considered as being paired with itself.

Claim 1: No line L can contain both a point and its pairing. For then there would only be at most three paired points outside L, together with the central point *; and these four points can't be enough to form a line whenever a point of L is erased.

Claim 2: Any line L going through the central point * must map to a line that also goes through . For the pairs of the four non- points in L would otherwise not be enough to form a line whenever a non-* point of L is erased. Thus, if we call the union of Row 3, Column 3, and the two diagonals the asterisk-set, then points in (resp. outside) the asterisk-set must pair with points in (resp. outside) the asterisk set.

Claim 3: Any line L not going through * must map to a disjoint (and therefore parallel) line. For there are at most 6 X's outside the line; if four of these form a line K, intersecting L at point p, say, then erasing point p will leave the grid without a line (because the two remaining points, together with at most one point from L and one point from K, are not enough to form a line).

Claim 4: Any line L not going through * must map to a disjoint parallel line not going through *. For Claim 2 tells us that lines going through * map to lines going through *, and the pairing function is its own inverse.

Now, consider Row 1 and the row that it maps to under the pairing: Row r, say. The vertical bisector of the grid (Column 3) intersects these rows at points p1 and pr, say. Points on Row 1 not equal to p1 pair with points on Row r not equal to pr; so p1 must map to pr. This contradicts Claim 1. So there can be no such pairing. QED

This proof works for any odd n >= 5. It doesn't work for n=3, because Claim 3 fails: the two remaining points, together with at most one point from L and one point from K, are indeed enough to form a line.

Well, but one player has to have a winning strategy! Which one? We can answer this fairly easily for n=5, by brute force computer search, working backwards from the filled board by flagging all positions as winning or losing. There are only 2^25 positions to consider, and the search takes about 30 seconds on my laptop. It turns out that the 5x5 board is a win for P1, who can make any initial move. (By contrast, in the 3x3 board the only winning move is the central point *.) This tells us two things: (i) P1 wins; (ii) the winning strategy is not a simple pairing.

Next stop: 6x6. This may take a while.