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.

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

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:

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