Wednesday, September 3, 2014

September 3

M x Ns:

Conjecture: For any mxn grid where m or n is equivalent to 2 (mod 3), we can fill the grid with Xs and Os such that through a reflection over the vertical, we arrive at another XO pattern where the corresponding number grids to both the original XO grid and the reflected XO grid are the same.

To prove the above, I first want to show that in any mxn grid we can fill the first and mth row with X(OXX)...(OXX)O and O(XXO)...(XXO)X, correspondingly, and from there we can fill the rest of the grid.

m=1: (and n is equivalent to 2 (mod 3)) The first (and only) row is XOXX...OXXO. Reflecting over the vertical, we get OXXO...XXOX. We know these produce the same number grid, which is [{122...221}].

m=2: 

XOXX...OXXO
OXXO...XXOX

Reflecting gives:

OXXO...XXOX
XOXX...OXXO

The number grid is [{2444...4442}{2444...4442}].

m=3 (and n is equivalent to 2 (mod 3))
XOXX...OXXO
...
OXXO...XXOX

If the "..." is filled in such in a symmetrical way, the number grid will remain the same when we reflect the XO grid. Basically, the ith slot in the second row and the (n-i+1)th slot should both have an X or both have an O. 


This is because the ith and the (n-i+1)th slot in the 2nd row are in contact with the same number of Xs from the 1st and 3rd rows. This means that if the pattern of XOs in the 2nd row is symmetrical, then the ith and the (n-i+1)th slots will have the same number. 

If n is not equivalent to 2 (mod 3) then the full X(OXX)...(OXX)O pattern in row 1 and the O(XXO)...(XXO)X pattern in row 3 will not fit. Thus slots i and (n-i+1) are not always in contact with the same number of Xs from the 1st and 3rd rows. Thus the number grid cannot be symmetrical, and we cannot reflect the XO grid to produce another XO grid with the same numbers corresponding to it. In other words, if n is not equivalent to 2 (mod 3) when m=3, then the grid would not be unsolvable.

For m>3 (when m is not equivalent to 2 (mod 3) and n is equivalent to 2 (mod 3))

Note: for the case when n is not equivalent to 2 (mod 3) while m is equivalent, the explanation is the same but only "rotated." (if that makes sense...)

If we keep going, adding rows, this pattern holds. But the "..." between the rows of XOXX..OXXO and OXXO..XXOX has to be symmetrical across the vertical axis. 

The number of Xs in row 1 that (i, 2) is adjacent to the same number of Xs in row 1 that (n-i+1, 2) is adjacent to. Thus if row 2 is symmetrical, then the number grid corresponding to row 1 will be symmetrical. So we want row 2 to be symmetrical.

If we look at row 3, now knowing that row 2 is symmetrical, we know that (i, 3) is adjacent to the same number of Xs in row 2 that (n-i+1, 3) is adjacent to. Thus if row 3 is symmetrical, then the number grid corresponding to row 2 will be symmetrical as well.

Now if we look at row j such that j is less than m-1 (the row right before the mth row is a little bit different.) Anyway, let's assume that we know row j-1 and row j-2 are symmetrical in XOs. Thus, in row j, we know that (i, j) and (n-i+1, j) are adjacent to the same number of Xs in row j-1. If row j is symmetrical, then (i-1, j) = (n-i+2, j), (i, j) = (n-i+1, j), and (i+1, j) = (n-i, j). Thus the numbers corresponding to (i, j-1) and (n-i+1, j) are the same. This applies even if i-1 or i+1 are equal to 0 or greater than n.  

In summary, if rows j-1 and j-2 are symmetrical in XOs, then if row j is symmetrical, the number grid for row j-1 is symmetrical.


Now let's look at the case where j = m-1. Let us assume that row j-1 is symmetrical. We also know that (i, j) and (n-i+1, j) are adjacent to the same number of Xs in row m and in row j-1. Thus the number grid for row j is symmetrical if j is symmetrical. (In addition, we still know that the number grid for row j-1 is symmetrical if j-1 and j-2 are symmetrical in XOs).

If every row other than row 1 and row m is symmetrical, we know that all of the number grids are symmetrical.  We also know that rows 1 and m are not symmetrical. If we reflect the whole grid over the vertical axis, the number grid will remain the same. This is because rows 2 through m-1 are symmetrical over the vertical, so it doesn't matter, and the grids next to rows 1 or m are adjacent to the same number of Xs in that row.

Here's a picture of row 1 and the row below it showing how many Xs each grid square is adjacent to. We notice that this pattern is symmetrical. Thus by flipping row 1, the numbers in the adjacent row remain the same. 



Both m and n are 2 (mod 3)

Is a special case. While the above method works, it is interesting to consider filling both row 1 and m and columns 1 and n with the O(XXO)...(XXO)X or X(OXX)...(OXX)O pattern. If we start with the outermost grid squares filled in this manner, we can no longer rely on vertical or horizontal symmetry. This is where the diagonal pattern would come in.

1 comment:

  1. I think you have a way of generating cases that are not solvable for the cases that don't work. We may have you go back to this after you've done more induction to try it that way and see if we can get it to be more elegant, but it's convincing now. Forrest might still suggest changes, not sure.

    You've had to use the condition of 2 mod 3 in this proof, but I don't think your way of generating them is creating the only non-solvable puzzles, which means we haven't begun to try to prove that the puzzles that are 1 mod 3 or 0 mod 3 in both dimensions do work. That's probably going to be harder, but may be something to start thinking about.

    Another avenue that might be more fun (if the above suggestion gets frustrating) is to play around with different puzzle shapes. Instead of the squares, what if you had an equilateral triangle lattice, a hexagon lattice, or some other lattice you design...? Using the same rules what would make those puzzles solvable/unsolvable. We don't have the answers to these questions.

    ReplyDelete