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 or horizontal axis, 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: The first (and only) row is XOXX...OXXO. Reflecting over the vertical, we get OXXO...XXOX. We know these produce the same number grids.
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.
If we keep going, adding rows, this pattern holds. But the "..." between the rows of XOXX..OXXO and OXXO..XXOX has to follow the diagonal matching pattern (sorta like the 8x8 in the last post).
Tuesday, September 2, 2014
Friday, August 29, 2014
August 29
NxMs:
Conjecture:
If
or
then the m by n grid is unsolvable.
[Also, side note: m refers to column, n refers to row. This is because of the proper alphabetical order and the usual way of referring to things as row then column.]
Examples that I have (some) solutions for.
1] m x 1:
Numbers: [{1 2 2 ... 2 1}]
XO grids: [{XOXX...OXXO}] and [{OXXO...XXOX}]
2] m x 2:
Numbers: [{2 3 3 ... 3 2}{2 3 3 ... 3 2}]
XO grids: [{XOXO...}{OXOX...}], [{OXOX...}{XOXO...}], [{XXX...}{OOO...}], [{OOO...}{XXX...}]
3] 5 x 3:
Numbers: [{2 3 4 3 2}{3 5 6 5 3}{2 3 4 3 2}]
XO grids: [{XOXXO}{OXOXO}{OXXOX}], [{OXXOX}{OXOXO}{XOXXO}] + possibly others
4] 8x8:
Grids shown below:
A few of these I have after doing the 5 x 3 case, which is why a few are specific to odd ms and ns.
Conjecture:
If
or
then the m by n grid is unsolvable.
[Also, side note: m refers to column, n refers to row. This is because of the proper alphabetical order and the usual way of referring to things as row then column.]
Examples that I have (some) solutions for.
Numbers: [{1 2 2 ... 2 1}]
XO grids: [{XOXX...OXXO}] and [{OXXO...XXOX}]
2] m x 2:
Numbers: [{2 3 3 ... 3 2}{2 3 3 ... 3 2}]
XO grids: [{XOXO...}{OXOX...}], [{OXOX...}{XOXO...}], [{XXX...}{OOO...}], [{OOO...}{XXX...}]
3] 5 x 3:
Numbers: [{2 3 4 3 2}{3 5 6 5 3}{2 3 4 3 2}]
XO grids: [{XOXXO}{OXOXO}{OXXOX}], [{OXXOX}{OXOXO}{XOXXO}] + possibly others
4] 8x8:
Grids shown below:
A few of these I have after doing the 5 x 3 case, which is why a few are specific to odd ms and ns.
- In the number grid, the numbers increase towards the center, both horizontally and vertically.
- The two solutions are reflections of each other over either the vertical or horizontal axis (so far, I think that both transformations yield the same result, so either gets from one solution to the other)
- The number of solutions pairs (those that are reflections of each other) is related to n, the number of columns. At the moment, I believe it is the number of columns.
- In the case where n and m are odd, the middle row and column will be the same in both solutions. (I'm not sure how this works yet if they're even. Maybe it doesn't. Yeah, I don't think it does, because of the m x 2s.)
- If m and/or n are odd, the pattern of Xs and Os will be alternating in the middle row/column. (I am unsure about this.)
- In any m x n and in any vertical or horizontal group of three, there will be at least one O and one X. (Also unsure about this one.)
- The patterns for the rows will be either O+XXOs+X, X+OXXs+O, XOXO... or OXOX. (Again, unsure...)
Thursday, August 28, 2014
August 28
Nx1s:
In the case that

then the number grid pattern [1, 2,....2,1] will be unsolvable; there are (n-2) 2s.
The unsolvable pattern is XO and then repeating XXOs or the reverse: OXXs then an OX at the end. For example, the number grid that corresponds to XOXXOXXO is [{1 2 2 2 2 2 2 1}]. From that same number grid, we can also produce the XO pattern: OXXOXXOX.
If we take the pattern [{1 2 2 2 ... 2 1}] where there are (n-2) 2s. At slots 1 and n there are 1s. Thus, in the kth slot, there is a 2. In slots k-1, k, and k+1, there must be two Xs. This can either happen as OXX, XOX, or XXO. If the kth slot is an X, then as we move along the 2s in the number grid, the pattern will repeat. If we start with OXX centered on the kth slot, then as we move one way or the other the OXXs repeat. Similarly, if we start with XXO, the XXOs will repeat.
If the kth slot is an O, as we move we will see either of the two patterns. From XOX we can form either XOXO or XOXX; this indicates whether the repeating three-symbol pattern is OXX or XXO.
Conjecture: If
then the n by 1 grid is always solvable.
NxMs:
Conjecture:
If

or

then the n by m grid is unsolvable.
For n x 1, the pattern is [{1 2 .... 2 1}] and for n x 2, the pattern is [{2 3 ... 3 2}{2 3...3 2}].
So in the 1st and the nth slot of any row, the number is one less than it is elsewhere. Let's call this digit a. (So for n x 1, the pattern is [{a (a+1) (a+1)...(a+1) a}]). The numbers towards the middle of the grid are higher.
For a grid square on the edge of the grid (that's not a corner) the most Xs in its vicinity is 6; for a corner, that number is 4.
In the case that
then the number grid pattern [1, 2,....2,1] will be unsolvable; there are (n-2) 2s.
The unsolvable pattern is XO and then repeating XXOs or the reverse: OXXs then an OX at the end. For example, the number grid that corresponds to XOXXOXXO is [{1 2 2 2 2 2 2 1}]. From that same number grid, we can also produce the XO pattern: OXXOXXOX.
If we take the pattern [{1 2 2 2 ... 2 1}] where there are (n-2) 2s. At slots 1 and n there are 1s. Thus, in the kth slot, there is a 2. In slots k-1, k, and k+1, there must be two Xs. This can either happen as OXX, XOX, or XXO. If the kth slot is an X, then as we move along the 2s in the number grid, the pattern will repeat. If we start with OXX centered on the kth slot, then as we move one way or the other the OXXs repeat. Similarly, if we start with XXO, the XXOs will repeat.
If the kth slot is an O, as we move we will see either of the two patterns. From XOX we can form either XOXO or XOXX; this indicates whether the repeating three-symbol pattern is OXX or XXO.
Conjecture: If
NxMs:
Conjecture:
If
or
then the n by m grid is unsolvable.
For n x 1, the pattern is [{1 2 .... 2 1}] and for n x 2, the pattern is [{2 3 ... 3 2}{2 3...3 2}].
So in the 1st and the nth slot of any row, the number is one less than it is elsewhere. Let's call this digit a. (So for n x 1, the pattern is [{a (a+1) (a+1)...(a+1) a}]). The numbers towards the middle of the grid are higher.
For a grid square on the edge of the grid (that's not a corner) the most Xs in its vicinity is 6; for a corner, that number is 4.
Tuesday, August 26, 2014
August 26
Nx1s:
If

then the n by 1 grid is always solvable. In the case that

then the number grid pattern [1, 2,....2,1] will be unsolvable; there are n-2 2s.
The unsolvable pattern is XO and then repeating XXOs or the reverse, with OXXs then an OX at the end. For example, XOXXOXXO can be written as [{1 2 2 2 2 2 2 1}]. Another arrangement of Xs and Os that produces the same number grid is OXXOXXOX. Actually, in the definitions of transformations I gave in the previous post (August 21) these two would be the same. Perhaps I should redefine which transformations are considered the same...
Anyway, assuming we consider these different: the pattern of 1,2,...2,1 is unsolvable when the number of grid squares is equivalent to 2 mod 3, because of the two ways it can be translated into Xs and Os. To have a pattern with more than one "solution" there must be some Os and some Xs. If it were only Xs or only Os, then there is no possible way to have another solution. Since this is n x 1, the range of squares next to any given one is only 3, as demonstrated below where the orange one is the one we're focused on.
Knowing that there must be an O and an X somewhere in the entire line, let's pretend we're centered on an O. The pattern of the three highlighted would then be XOX. So the number for this square would be 2. Let us call the grid of numbers N and the one grid of Xs and Os A and the other B for simplicities sake. Now we know that in the kth –let k be equivalent to 1 mod 3– slot in A, there is an O and in the (k-1)th and (k+1)th there are Xs. Also, in N there is a 2 in the kth slot so we know that there are 2 Xs in the (k-1), k, and (k+1) slots in B. The pattern in these three must be either XXO or OXX.
Let's say that the pattern is XXO. From our knowledge of the pattern in A, we know that k-1 in N is either one or 2. Now that we have the pattern in B as well, we know that the number at k-1 in N is greater than or equal to 2. From this, we know that the number at k-1 in N is 2. From there, we can figure out what k-2 is in A and so on.
In short:
A is green
B is pink
XOX -> _2_ -> XXO -> 22_ -> XXOX -> 222_ (if try 322_, there is a contradiction) -> XOXXO -> 2222_ etc...
We see that in A the pattern XOX repeats and in B the pattern XXO repeats. Since we said k was 1 mod 3, then when we get down to slots 2 and 1, the full pattern won't fit. At this point, A = _ _ XOXXO... and B = _ _ XXOXX... and N = _ _ 2 2 2 2... From there, we get that A = _ XXOXXO... and B = _ OXXOXX... There is only one way to finish these sequences such that the values for N don't conflict. A is thus OXXOXX... and B is thus XOXXO... and N is 1 2 2 2 ...
Since k is 1 mod 3, if we go the other way trying to find the pattern, we discover that the full 3 symbol pattern fits and N thus ends ... 2 2 2 1.
We can also work with k if k is equivalent to 2 mod 3. In this case, the pattern for B has to be OXX. The process is otherwise similar.
If
then the number grid pattern [1, 2,....2,1] will be unsolvable; there are n-2 2s.
The unsolvable pattern is XO and then repeating XXOs or the reverse, with OXXs then an OX at the end. For example, XOXXOXXO can be written as [{1 2 2 2 2 2 2 1}]. Another arrangement of Xs and Os that produces the same number grid is OXXOXXOX. Actually, in the definitions of transformations I gave in the previous post (August 21) these two would be the same. Perhaps I should redefine which transformations are considered the same...
Anyway, assuming we consider these different: the pattern of 1,2,...2,1 is unsolvable when the number of grid squares is equivalent to 2 mod 3, because of the two ways it can be translated into Xs and Os. To have a pattern with more than one "solution" there must be some Os and some Xs. If it were only Xs or only Os, then there is no possible way to have another solution. Since this is n x 1, the range of squares next to any given one is only 3, as demonstrated below where the orange one is the one we're focused on.
Knowing that there must be an O and an X somewhere in the entire line, let's pretend we're centered on an O. The pattern of the three highlighted would then be XOX. So the number for this square would be 2. Let us call the grid of numbers N and the one grid of Xs and Os A and the other B for simplicities sake. Now we know that in the kth –let k be equivalent to 1 mod 3– slot in A, there is an O and in the (k-1)th and (k+1)th there are Xs. Also, in N there is a 2 in the kth slot so we know that there are 2 Xs in the (k-1), k, and (k+1) slots in B. The pattern in these three must be either XXO or OXX.
Let's say that the pattern is XXO. From our knowledge of the pattern in A, we know that k-1 in N is either one or 2. Now that we have the pattern in B as well, we know that the number at k-1 in N is greater than or equal to 2. From this, we know that the number at k-1 in N is 2. From there, we can figure out what k-2 is in A and so on.
In short:
A is green
B is pink
XOX -> _2_ -> XXO -> 22_ -> XXOX -> 222_ (if try 322_, there is a contradiction) -> XOXXO -> 2222_ etc...
We see that in A the pattern XOX repeats and in B the pattern XXO repeats. Since we said k was 1 mod 3, then when we get down to slots 2 and 1, the full pattern won't fit. At this point, A = _ _ XOXXO... and B = _ _ XXOXX... and N = _ _ 2 2 2 2... From there, we get that A = _ XXOXXO... and B = _ OXXOXX... There is only one way to finish these sequences such that the values for N don't conflict. A is thus OXXOXX... and B is thus XOXXO... and N is 1 2 2 2 ...
Since k is 1 mod 3, if we go the other way trying to find the pattern, we discover that the full 3 symbol pattern fits and N thus ends ... 2 2 2 1.
We can also work with k if k is equivalent to 2 mod 3. In this case, the pattern for B has to be OXX. The process is otherwise similar.
Thursday, August 21, 2014
August 21
Nx1s:
Written with mod...
If

then the n by 1 grid is always solvable. In the case that

then the number grid pattern [1, 2,....2,1] will be unsolvable; there are n-2 2s.
NxMs:
Since nx1 isn't solvable when n is equivalent to 2 mod 3, then nxms might not be solvable if n or m is 2 mod 3.
From the data I have so far, k x 1 (where k = 2, 5,8,etc...) are unsolvable and n x 2 are unsolvable (and 2 is 2 mod 3), which indicates that the above might be true. I don't really have any reasons as to why that might be true yet, but I'll think about it.
TRANSFORMATIONS:
With the transformations, this is what I was thinking: 1) reflections over the vertical, the horizontal, and the diagonal (as in from corner to corner diagonal, which only applies to square grids and is a combination of rotations and other flipping....) lines are the same, 2) rotations by multiples of 90 degrees are the same. What I typed earlier, [XO,XO]=[OX,OX]=[XO,OX]=[OX,XO], was an error; I meant that [XO,XO]=[OX,OX] and [XO,OX]=[OX,XO]. There isn't a simple transformation that would get from the second to the third.
I would consider these to be the same, though:
A higher dimension example would be (though there would be others grids in a complete list of "sames"):
Written with mod...
If
then the number grid pattern [1, 2,....2,1] will be unsolvable; there are n-2 2s.
NxMs:
Since nx1 isn't solvable when n is equivalent to 2 mod 3, then nxms might not be solvable if n or m is 2 mod 3.
From the data I have so far, k x 1 (where k = 2, 5,8,etc...) are unsolvable and n x 2 are unsolvable (and 2 is 2 mod 3), which indicates that the above might be true. I don't really have any reasons as to why that might be true yet, but I'll think about it.
TRANSFORMATIONS:
With the transformations, this is what I was thinking: 1) reflections over the vertical, the horizontal, and the diagonal (as in from corner to corner diagonal, which only applies to square grids and is a combination of rotations and other flipping....) lines are the same, 2) rotations by multiples of 90 degrees are the same. What I typed earlier, [XO,XO]=[OX,OX]=[XO,OX]=[OX,XO], was an error; I meant that [XO,XO]=[OX,OX] and [XO,OX]=[OX,XO]. There isn't a simple transformation that would get from the second to the third.
I would consider these to be the same, though:
A higher dimension example would be (though there would be others grids in a complete list of "sames"):
Wednesday, August 20, 2014
August 20
I looked over the nx1s again. It appears that if n is 2 more than (or one less than) a multiple of 3, it is not necessarily solvable. The pattern of numbers that makes this so is 1s with 2s in the middle; in particular, the number of 2s is appears to be a multiple of three. From there, looking at the patterns of Xs and OS that can be generated, they're in the form of repeating XXOs with an O and an X at the end. I'm assuming that these qualify as unsolvable even though the two solutions are reflections. If transformations like this are counted as the same, then these would be "solvable."
I also looked over the counts for "without transformations" for nx1s and revised the formula. I think it works now, but I'm not completely sure.
Tuesday, August 19, 2014
August 19
Today, I worked on finding the number of configurations without transformations (as in, XO=OX and [XO,XO]=[OX,OX]=[XO,OX]=[OX,XO]) The pattern for when n is variable and m=1 was relatively simple after connecting it to Pascal's triangle and then realizing that the sums of rows in Pascal's are just powers of 2. The pattern for when m=2 has been a bit more difficult to figure out, and I'm not sure if what I have written is accurate, because I haven't finished working with the 4x2 and 5x2 cases.
In addition, I corrected one mistake: 4x4 is indeed solvable. The example I had was incorrect. I assume the other mistake was in the 3x3 but have not had the chance to take a look at that as of yet.
I also added a row at the bottom for nxm but haven't really done much there yet.
Subscribe to:
Posts (Atom)






