Square cells in a rectangular grid; neighborhood defined as edges, vertices, but not self.
From an earlier post, I had these determinants, and I just added more.
For 1 x n, the determinants were:
1x1: 0
1x2: -1
1x3: 0
1x4: 1
1x5: 0
1x6: -1
The pattern: for n equiv 0 (mod 2), the determinant is either -1 or 1. (We have proved this to be true.)
For 2 x n, the determinants were:
1x2: -1
2x2: -3 = -1*3
2x3: 7 (4th prime)
2x4: 5 (3rd prime)
2x5: -33 = -1*3*11
2x6: 13 (6th prime)
2x7: 119 = 7 * 17
2x8: -171 = -1*3*57
2x9: -305 = 5 * 61
It appears that the absolute value of all these determinants is either prime or the product of 2 primes.
And for 3 x n, determinants:
3x3: 0
3x4: 9 = 3^2
3x5: 0
3x6: -497 = 7*71
3x7: 0
3x8: -8687 = 7*241
Friday, December 12, 2014
Thursday, December 11, 2014
December 11
Square cells in a rectangular grid; neighborhood defined as edges, vertices, but not self.
These are the blocks:
0 1 0…
1 0 1…
0 1 0…
1 1 0…
1 1 1…
0 1 1…
0 0 0…
0 0 0…
0 0 0…
To see the pattern, let the first of the blocks be A, the second B, and the third C.
The 3x3 adjacency matrix:
A B C
B A B
C B A
The 3x4 adjacency matrix:
0 1 0 0 1 1 0 0 0 0 0 0
1 0 1 0 1 1 1 0 0 0 0 0
0 1 0 1 0 1 1 1 0 0 0 0
0 0 1 0 0 0 1 1 0 0 0 0
1 1 0 0 0 1 0 0 1 1 0 0
1 1 1 0 1 0 1 0 1 1 1 0
0 1 1 1 0 1 0 1 0 1 1 1
0 0 1 1 0 0 1 0 0 0 1 1
0 0 0 0 1 1 0 0 0 1 0 0
0 0 0 0 1 1 1 0 1 0 1 0
0 0 0 0 0 1 1 1 0 1 0 1
0 0 0 0 0 0 1 1 0 0 1 0
So, if we think about it in terms of the blocks, a 3x4 looks like:
A B C
B A B
C B A
Which is the same as the 3x3. We can note that the blocks are now 3x4 instead of 3x3 like they were for the 3x3.
Now, let's look at a 4x4:
0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0
1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0
0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0
0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0
0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0
0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0
If we convert to blocks, the 4x4 looks like:
A B C C
B A B C
C B A B
C C B A
Now, let's think about what the blocks are. A is the 1xn adjacency matrix for square cells in a rectangular grid including edges and not self, and C is all 0s. B is a 1xn adjacency matrix for square cells in a rectangular grid including edges and self. This is interesting.
I'm not sure how we can find the determinant…
These are the blocks:
0 1 0…
1 0 1…
0 1 0…
1 1 0…
1 1 1…
0 1 1…
0 0 0…
0 0 0…
0 0 0…
To see the pattern, let the first of the blocks be A, the second B, and the third C.
The 3x3 adjacency matrix:
A B C
B A B
C B A
The 3x4 adjacency matrix:
0 1 0 0 1 1 0 0 0 0 0 0
1 0 1 0 1 1 1 0 0 0 0 0
0 1 0 1 0 1 1 1 0 0 0 0
0 0 1 0 0 0 1 1 0 0 0 0
1 1 0 0 0 1 0 0 1 1 0 0
1 1 1 0 1 0 1 0 1 1 1 0
0 1 1 1 0 1 0 1 0 1 1 1
0 0 1 1 0 0 1 0 0 0 1 1
0 0 0 0 1 1 0 0 0 1 0 0
0 0 0 0 1 1 1 0 1 0 1 0
0 0 0 0 0 1 1 1 0 1 0 1
0 0 0 0 0 0 1 1 0 0 1 0
So, if we think about it in terms of the blocks, a 3x4 looks like:
A B C
B A B
C B A
Which is the same as the 3x3. We can note that the blocks are now 3x4 instead of 3x3 like they were for the 3x3.
Now, let's look at a 4x4:
0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0
1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0
0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0
0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0
0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0
0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0
If we convert to blocks, the 4x4 looks like:
A B C C
B A B C
C B A B
C C B A
Now, let's think about what the blocks are. A is the 1xn adjacency matrix for square cells in a rectangular grid including edges and not self, and C is all 0s. B is a 1xn adjacency matrix for square cells in a rectangular grid including edges and self. This is interesting.
I'm not sure how we can find the determinant…
Monday, December 1, 2014
December 1
Square cells in a rectangular grid; neighborhood defined as edges, vertices, but not self.
Let's look at the adjacency matrix for a 3x3.
0 1 0 1 1 0 0 0 0
1 0 1 1 1 1 0 0 0
0 1 0 0 1 1 0 0 0
1 1 0 0 1 0 1 1 0
1 1 1 1 0 1 1 1 1
0 1 1 0 1 0 0 1 1
0 0 0 1 1 0 0 1 0
0 0 0 1 1 1 1 0 1
0 0 0 0 1 1 0 1 0
This seems to be made of the following blocks:
0 1 0
1 0 1
0 1 0
1 1 0
1 1 1
0 1 1
0 0 0
0 0 0
0 0 0
To see the pattern, let the first of the blocks be A, the second B, and the third C. From this, the adjacency matrix for a 3x3 is:
A B C
B A B
C B A
So we see that the diagonal is made up of As.
Let's look at the adjacency matrix for a 3x3.
0 1 0 1 1 0 0 0 0
1 0 1 1 1 1 0 0 0
0 1 0 0 1 1 0 0 0
1 1 0 0 1 0 1 1 0
1 1 1 1 0 1 1 1 1
0 1 1 0 1 0 0 1 1
0 0 0 1 1 0 0 1 0
0 0 0 1 1 1 1 0 1
0 0 0 0 1 1 0 1 0
This seems to be made of the following blocks:
0 1 0
1 0 1
0 1 0
1 1 0
1 1 1
0 1 1
0 0 0
0 0 0
0 0 0
To see the pattern, let the first of the blocks be A, the second B, and the third C. From this, the adjacency matrix for a 3x3 is:
A B C
B A B
C B A
So we see that the diagonal is made up of As.
Monday, October 27, 2014
October 27
Square cells in a rectangular grid, the neighborhood defined as edges, vertices, but not self
1 x n:
A 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
Taking the determinant by the first column would result in the negative determinant of:
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...
By using the first column again, we would subtract the determinant of:
0 1 0 0 0 ...
1 0 1 0 0 ...
0 1 0 1 0 ...
from the determinant of:
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...
Now, the base cases...
Let A_k be the adjacency matrix for a 1 x k grid.
A_1 = 0
det(A_1) = 0
A_2 =
0 1
1 0
det(A_2) = -1
A_3 =
0 1 0
1 0 1
0 1 0
det(A_3) = 0
A_4 =
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
det(A_4) = 1
We want to show that:
det(A_k) = 0 - det(A_(k-2)) = det(A_(k-2))
This works for A_3 and A_4:
det(A_3) = - det(A_1) = 0
det(A_4) = - det(A_2) = - (-1) = 1
So we assume that this holds for all A_i for i < or = k, and we want to show that this holds for A_(k+1).
A_(k+1) looks like this:
0 1 0 ...
1 0 1 ...
and so on.
If we take the determinant by the first column,
det(A_(k+1)) = -det(
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...)
= det(
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...)
-
0 1 0...
1 0 1 ...
= 0 - det(A_(k-1))
1 x n:
A 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
Taking the determinant by the first column would result in the negative determinant of:
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...
By using the first column again, we would subtract the determinant of:
0 1 0 0 0 ...
1 0 1 0 0 ...
0 1 0 1 0 ...
from the determinant of:
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...
Let A_k be the adjacency matrix for a 1 x k grid.
A_1 = 0
det(A_1) = 0
A_2 =
0 1
1 0
det(A_2) = -1
A_3 =
0 1 0
1 0 1
0 1 0
det(A_3) = 0
A_4 =
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
det(A_4) = 1
We want to show that:
det(A_k) = 0 - det(A_(k-2)) = det(A_(k-2))
This works for A_3 and A_4:
det(A_3) = - det(A_1) = 0
det(A_4) = - det(A_2) = - (-1) = 1
So we assume that this holds for all A_i for i < or = k, and we want to show that this holds for A_(k+1).
A_(k+1) looks like this:
0 1 0 ...
1 0 1 ...
and so on.
If we take the determinant by the first column,
det(A_(k+1)) = -det(
1 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0...
0 0 1 0 ...)
= det(
0 0 0 0 ...
1 0 1 0 ...
0 1 0 1 ...
0 0 1 0 ...)
-
0 1 0...
1 0 1 ...
= 0 - det(A_(k-1))
Friday, October 24, 2014
October 24
Square cells in a rectangular grid, the neighborhood defined as edges, vertices, but not self
1 x n:
If we look at the adjacency matrices, the diagonal is always 0s because self is not included.
So for a 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
If we take the determinant, we can use the first column, which leaves us taking the determinant of:
1 0 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
If we us the first column again, we add the determinants of:
0 1 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0 0...
0 0 1 ...
and:
0 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 ....
0 0 1 0 1...
The first of these looks the same as what we started with, and the second has a row of 0s so its determinant is 0.
1 x n:
If we look at the adjacency matrices, the diagonal is always 0s because self is not included.
So for a 1 x n, the matrix looks something like:
0 1 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
0 0 0 1 0 1 0...
If we take the determinant, we can use the first column, which leaves us taking the determinant of:
1 0 0 0 0 0 0...
1 0 1 0 0 0 0...
0 1 0 1 0 0 0...
0 0 1 0 1 0 0...
If we us the first column again, we add the determinants of:
0 1 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 0 0...
0 0 1 ...
and:
0 0 0 0 0 0...
1 0 1 0 0 0...
0 1 0 1 ....
0 0 1 0 1...
The first of these looks the same as what we started with, and the second has a row of 0s so its determinant is 0.
Thursday, October 23, 2014
October 23
For 1 x n, the determinants were:
1x1: 0
1x2: -1
1x3: 0
1x4: 1
1x5: 0
1x6: -1
The pattern: for n equiv 0 (mod 2), the determinant is either -1 or 1
For 2 x n, the determinants were:
2x2: -3
2x3: 7
2x4: 5
2x5: -33
And for 3 x n, determinants:
3x3: 0
3x4: 9
3x5: 0
I'm not sure what it is for mxn yet.
But I think that this is the rule for solvability: it seems that for 1xm, if m is even it's solvable. In general, it seems that if one or both dimensions are even, then the puzzle is solvable.
I'll work on the nx1 case next time.
Tuesday, October 7, 2014
October 7
Revised version of the sidelength 3 case:
Matrices:
If we start to look at the determinant... Also, just as a note, this is how I was numbering the cells [in increasing order from left to right by row.]
Here is the side length of 2 case:
The determinant is clearly 0. One thing we can note about the starting matrix, is that it has a diagonal of 0s and it is symmetrical over that diagonal. Since we can take either row or column to do the determinant by, in the following case, there is always either a row or column that has only one 1 in it. If we take that, it is simple to do the determinant.
Here is the side length 3 case:
Now, we see that there is a column of all 0s. If we did the determinant by this column, the result will clearly be 0.
To make the result more clear: (The green is the column I went down to take the determinant, the orange is the row that was ignored for the only 1 there.)
...not sure how helpful this is.
Thinking about Triangles:
In any given triangle, we know that the bottom row looks like this:
Now, if we have the numbers filled in like this:
So for the kth cell in this row, the number a_k is equal to 1 if k is even or 0 if k is odd.
If k is odd, then the kth slot is a 0 and the (k-1)th and (k+1)th slots are 1. The rest of the grid is filled with Os, so all Xs have to be in the bottom row. From the 1s, we know there has to be an X in some of the following slots: (k-2), k, (k+2). This particular area is ambiguous.
If k is even, then the kth slot is a 1 and the (k-1)th and (k+1)th are 0. From here, we know that either (k-1) or (k+1) contains an X.
Friday, October 3, 2014
October 3
Triangles in a triangle arrangement with the neighborhood defined by edges and counting self.
We used Python to see that the determinants of the association matrices are powers of 2 alternating from positive to negative interleaved by 0s once the size of the triangle is greater than 4. (When the side length was 3, the pattern was disrupted.)
We used Python to see that the determinants of the association matrices are powers of 2 alternating from positive to negative interleaved by 0s once the size of the triangle is greater than 4. (When the side length was 3, the pattern was disrupted.)
n = 1, det = 1
n = 2, det = -2
n = 3, det = -4
n = 4, det = 4
n = 5, det = 0
n = 6, det = -8
n = 7, det = 0
n = 8, det = 16
...
Triangles in a triangle arrangement with the neighborhood defined by edges
and not counting self.
Using Python, we discovered that the determinants were always 0, meaning that all of them should be unsolvable.
The bottom row is the highlighted one:
The number of the bottom row of the triangle is: 01010...10. This can be solved as either XOOOXOOO... or OOXOOOX... with the rest of the triangle being Os.
[I don't know if it would be easier to think of the bottom row as two different "rows," one of triangles pointing up, one of triangles pointing down. If we did consider them like that, the pattern would be XOXO... and all Os and then OXOX... and then all Os.]
For the sidelength of 1 case, we know that the number will always be 0, because it does not count itself. This is unsolvable because we do not know if the 1 triangle contains an X or an O.
For the sidelength of 2 case, we have:
For the sidelength of 3 case, we have:
For the sidelength of 4 case, we have:
Matrices (where n is the side length):
n=1: [0]
n=2:
The bottom row is the highlighted one:
The number of the bottom row of the triangle is: 01010...10. This can be solved as either XOOOXOOO... or OOXOOOX... with the rest of the triangle being Os.
[I don't know if it would be easier to think of the bottom row as two different "rows," one of triangles pointing up, one of triangles pointing down. If we did consider them like that, the pattern would be XOXO... and all Os and then OXOX... and then all Os.]
For the sidelength of 1 case, we know that the number will always be 0, because it does not count itself. This is unsolvable because we do not know if the 1 triangle contains an X or an O.
For the sidelength of 2 case, we have:
For the sidelength of 3 case, we have:
For the sidelength of 4 case, we have:
Matrices (where n is the side length):
n=1: [0]
n=2:
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0
n=3:
0 0 1 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0
1 1 0 1 0 0 0 0 0
0 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0
0 1 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 0
0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 0 1 0
....
Tuesday, September 30, 2014
September 30
Triangles in a triangle arrangement with the neighborhood defined by edges and counting self.
We used Python to see that the determinants of the association matrices are powers of 2 alternating from positive to negative interleaved by 0s once the size of the triangle is greater than 4. (When the side length was 3, the pattern was disrupted.)
Triangles in a triangle arrangement with the neighborhood defined by edges and not counting self.
Using Python, we discovered that the determinants were always 0, meaning that all of them should be unsolvable.
The number of the bottom row of the triangle is: 01010...10. This can be solved as either XOOOXOOO... or OOXOOOX...
Matrices (where n is the side length):
n=1: [0]
n=2:
We used Python to see that the determinants of the association matrices are powers of 2 alternating from positive to negative interleaved by 0s once the size of the triangle is greater than 4. (When the side length was 3, the pattern was disrupted.)
Triangles in a triangle arrangement with the neighborhood defined by edges and not counting self.
Using Python, we discovered that the determinants were always 0, meaning that all of them should be unsolvable.
The number of the bottom row of the triangle is: 01010...10. This can be solved as either XOOOXOOO... or OOXOOOX...
Matrices (where n is the side length):
n=1: [0]
n=2:
0 0 1 0
0 0 1 0
1 1 0 1
0 0 1 0
n=3:
0 0 1 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0
1 1 0 1 0 0 0 0 0
0 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0
0 1 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 0
0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 0 1 0
....
Thursday, September 11, 2014
September 11
Triangles-the triangle arrangement:
For the 8-triangle, I tried the recursing thing, but it doesn't seem to work. While I don't have a pattern for the triangles yet, I feel like there are more "layers" were with the squares. Then again, I'm not really sure.
Percentages:
As of yet, I'm not seeing a pattern here really...assuming I actually counted the unsolvable ones right (not sure.)
For the 8-triangle, I tried the recursing thing, but it doesn't seem to work. While I don't have a pattern for the triangles yet, I feel like there are more "layers" were with the squares. Then again, I'm not really sure.
Percentages:
As of yet, I'm not seeing a pattern here really...assuming I actually counted the unsolvable ones right (not sure.)
Tuesday, September 9, 2014
September 9
Triangles:
Triangle Arrangement:
It looks like I made a few mistakes in the table. Here is the new version:
The 'solutions' I had for the 4 case actually wouldn't work. Oops.
For the 5 case, I started out with this pattern in all 3 corners: [{O}{OXX}] (oriented so that if they whole 5-triangle was rotated it would appear to be the same.) The pattern on each of the three sides was OXOXXOXXO, and the center was simply filled symmetrically–when I say 'symmetrically' here, I'm referring to a pattern that, when rotated 120 or 240 degrees, appears the same.
While trying to solve other cases, I've noticed that may kind of recurse. For example, take the 8-triangle. If we sort of cut off the outermost row of triangles, we're left with a 5-triangle, which we know is unsolvable. Similarly, if we start with a 5-triangle and get rid of the outermost row, we're left with a 2-triangle, which we already knew was unsolvable. I haven't really done anything with this yet, but it might help...
I've tried working with the 8 case, but it doesn't work with the same method as the 5-triangle (putting the [{O}{OXX}] pattern in the three corners and then trying to fill the rest.) I think it might be better if I divide the 8 into 4 4-triangles, and make the 3 corner triangles rotations of each other such that the center one can be symmetrical... but I'm not sure that will work. Another thing to note, is that the 5-triangle doesn't divide nicely into 4 same-size triangles; so that might have something to do with solvability.
Also, with the 5 case, with the 3 corner patterns and edge pattern fixed, the middle could be filled in any way that was symmetrical, meaning there were a 3 solutions–the center being [{X}{XXX}],[{X}{XOX}], or [{O}{OOO}]. This would seem to indicate that, at least for the center, the ideas of increasing numbers towards the center and having no number over 3 are incorrect.
I also tried forcing solutions that were all 2s or all 1s, and it doesn't seem to work. The problem with the 2s is that the corners all have to be Xs, which makes filling the entire grid in an asymmetrical manner a bit difficult. With the 1s, 0s or 2s sneak in really easily...
Other:
I'll start looking into percentage of solvable/unsolvable in respect to the square case.
Also, another thing I thought of was, what if the cells weren't perfectly aligned (like a typical brick-like pattern)? It might be kind of difficult to notate and not particularly interesting.
Triangle Arrangement:
It looks like I made a few mistakes in the table. Here is the new version:
The 'solutions' I had for the 4 case actually wouldn't work. Oops.
For the 5 case, I started out with this pattern in all 3 corners: [{O}{OXX}] (oriented so that if they whole 5-triangle was rotated it would appear to be the same.) The pattern on each of the three sides was OXOXXOXXO, and the center was simply filled symmetrically–when I say 'symmetrically' here, I'm referring to a pattern that, when rotated 120 or 240 degrees, appears the same.
While trying to solve other cases, I've noticed that may kind of recurse. For example, take the 8-triangle. If we sort of cut off the outermost row of triangles, we're left with a 5-triangle, which we know is unsolvable. Similarly, if we start with a 5-triangle and get rid of the outermost row, we're left with a 2-triangle, which we already knew was unsolvable. I haven't really done anything with this yet, but it might help...
I've tried working with the 8 case, but it doesn't work with the same method as the 5-triangle (putting the [{O}{OXX}] pattern in the three corners and then trying to fill the rest.) I think it might be better if I divide the 8 into 4 4-triangles, and make the 3 corner triangles rotations of each other such that the center one can be symmetrical... but I'm not sure that will work. Another thing to note, is that the 5-triangle doesn't divide nicely into 4 same-size triangles; so that might have something to do with solvability.
Also, with the 5 case, with the 3 corner patterns and edge pattern fixed, the middle could be filled in any way that was symmetrical, meaning there were a 3 solutions–the center being [{X}{XXX}],[{X}{XOX}], or [{O}{OOO}]. This would seem to indicate that, at least for the center, the ideas of increasing numbers towards the center and having no number over 3 are incorrect.
I also tried forcing solutions that were all 2s or all 1s, and it doesn't seem to work. The problem with the 2s is that the corners all have to be Xs, which makes filling the entire grid in an asymmetrical manner a bit difficult. With the 1s, 0s or 2s sneak in really easily...
Other:
I'll start looking into percentage of solvable/unsolvable in respect to the square case.
Also, another thing I thought of was, what if the cells weren't perfectly aligned (like a typical brick-like pattern)? It might be kind of difficult to notate and not particularly interesting.
Monday, September 8, 2014
September 8
Triangle Arrangement:
(about like so:)
I've been working on the 6 case, and I'm not sure that it isn't solvable. So far, it seems that the pattern of numbers increasing towards the middle sort of holds. Also, the highest number is a 3, one less than the max.
Parallelogram Arrangement:
This one I haven't gotten into the higher number cases yet. But for the 1 by somethings, it appears to be the same pattern as for the rectangular.
Friday, September 5, 2014
September 5
M x Ns:
(when m and n are equivalent to 1 or 0 (mod 3))
The cases: [also, when I say "symmetrical" I mean reflecting over the vertical results in the same grid. Any proofs/reasons can be "rotated" to deal with symmetry over the horizontal.]
1] The number grid and the XO grid are symmetrical
2] The number grid is symmetrical, but the XO grid is not. But hey, this isn't actually possible when m and n aren't equivalent to 2 (mod 3)
3] The number grid isn't symmetrical, but the XO grid is.
4] The number grid and the XO grid are not symmetrical.
Case 1:
It has to be solvable.
Why? If we try to flip it, we get the same thing. If we try to 'solve' the number grid in such a way that the resulting XO is not symmetrical we'll run into issues... I guess I need to prove this. This is addressed under case 2.
Case 2:
Is impossible when m and n are equivalent to 1 or 0 (mod 3). (I think...)
For this to be possible, we need an asymmetrical XO grid such that every grid square (j, i) is adjacent to the same number of Xs that grid square (m-j+1, n-i+1) is.
Case 3:
This is also impossible.
Since the XO grid is symmetrical, the corresponding number to grid square (j, i) is the same as the corresponding number to grid square (m-j+1, n-i+1). Which would mean that the number grid has to be symmetrical.
Case 4:
Has to be solvable... I think.
Triangles!
Cells are adjacent if they share an edge. The highest number in any cell is 4. At the moment, I think unsolvability has to do with what shape is in the "center" of the grid–it can be either a hexagon or an "upside-down" triangle...though I really have nothing to base that on. And this is what I have so far:
(when m and n are equivalent to 1 or 0 (mod 3))
The cases: [also, when I say "symmetrical" I mean reflecting over the vertical results in the same grid. Any proofs/reasons can be "rotated" to deal with symmetry over the horizontal.]
1] The number grid and the XO grid are symmetrical
2] The number grid is symmetrical, but the XO grid is not. But hey, this isn't actually possible when m and n aren't equivalent to 2 (mod 3)
3] The number grid isn't symmetrical, but the XO grid is.
4] The number grid and the XO grid are not symmetrical.
Case 1:
It has to be solvable.
Why? If we try to flip it, we get the same thing. If we try to 'solve' the number grid in such a way that the resulting XO is not symmetrical we'll run into issues... I guess I need to prove this. This is addressed under case 2.
Case 2:
Is impossible when m and n are equivalent to 1 or 0 (mod 3). (I think...)
For this to be possible, we need an asymmetrical XO grid such that every grid square (j, i) is adjacent to the same number of Xs that grid square (m-j+1, n-i+1) is.
Case 3:
This is also impossible.
Since the XO grid is symmetrical, the corresponding number to grid square (j, i) is the same as the corresponding number to grid square (m-j+1, n-i+1). Which would mean that the number grid has to be symmetrical.
Case 4:
Has to be solvable... I think.
Triangles!
Cells are adjacent if they share an edge. The highest number in any cell is 4. At the moment, I think unsolvability has to do with what shape is in the "center" of the grid–it can be either a hexagon or an "upside-down" triangle...though I really have nothing to base that on. And this is what I have so far:
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.
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.
Subscribe to:
Posts (Atom)
















