Friday, December 12, 2014

December 12

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

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… 

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.

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))


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.

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.)

Since we have defined each cell's neighborhood as the cells around it touching by edges, but excluding itself, we know that the maximum number of 1s in any column or row of the association matrix is 3. We know that in taking the determinant of the association matrix we can always use the first column. This is because cell 1 is always only associated with cell 3, and no others. Then, as shown above, we can use the 1 in the new first column and produce a matrix with one column of all 0s.

...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.