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.





NxMs:

As far as I can tell, from the table, those that are unsolvable have number grids that are symmetrical both on the vertical and horizontal axes. And so far, it seems that if either n or (inclusive or) m is equivalent to 2 mod 3, then the grid is unsolvable.

I think this has something to do with the repeating patterns being 3 long and then needing 2 more on the end to complete the sequence so that it all works out. 


2 comments:

  1. Hi Katie! A couple observations:

    1) Your statement up top of what is to be proven (hypothesis) for Nx1s is good and correct, apart from a notational nitpick that I would put the (mod 3) afterward on the line, i.e. "n congruent-symbol 2 (mod 3)".

    Next, the question is, how much of that hypothesis you are trying to prove. To completely prove it, we would need to do two things:
    a) if n IS NOT congruent to 2 (mod 3), then the puzzle will always be uniquely solvable (FOR ANY POSSIBLE GRID OF NUMBERS!)
    b) if n IS congruent to 2 (mod 3), then the puzzle will not *always* be uniquely solvable (that is, there exists some grid of numbers for which there are multiple X/O grids that give the same result).

    To my mind, you prove (b) just with your opening paragraph of the proof.
    That is, you show there exists a number grid [1 (2 2 2) 1] (with the number of 2s being an exact multiple of 3) corresponding to both:
    X(OXX)(OXX)...(OXX)O
    O(XXO)(XXO)...(XXO)X

    I think one can simply observe that both of these X/O grids satisfy that same number grid, and (b) is proven.

    If you feel the need to be more rigorous, one could observe that both of these patterns have a 1 in the number grid at slots 1 and n, and also the kth slot of the number grid will equal 2 for both patterns, when 1 < k < n. Perhaps what you're doing later is along these lines? I had some difficulty following the latter portion of your proof though.

    However, I'm pretty sure that none of your proof addresses part (a) of the original statement. This is fine -- we weren't expecting you to prove part (a) (yet, anyway). (a) is a much harder thing to prove, because one has to show that the solutions is unique FOR ALL POSSIBLE GRIDs, and examining a single example of 1 2...2 1 grids cannot be sufficient. You may need some more advanced tools before you can properly attack that...

    However, it would be good if you took care in your proofs to state exactly the hypothesis you are proving, and then you can label the part that you *believe is true* but have not proved yet as a "conjecture".

    Finally, your generalized hypothesis for mxn grids is spot on. Great work there! Excellent pattern-finding!

    Next step: see if you can work up a generalized counter-example for mxn grids, similar to the 12221 grids for 1xn. (Once again, it's much harder to show that grids are uniquely solvable whenever m and n are both not congruent to 2 mod 3... so you may want to put that off for a while.)

    ReplyDelete
    Replies
    1. Katie said "As far as I can tell, from the table, those that are unsolvable have number grids that are symmetrical both on the vertical and horizontal axes."

      I thought that was a VERY interesting idea. Certainly the 1xn counter example is this way. I don't remember (or we may not have considered), whether the symmetry is always true. It would be cool to look into this more, try to find a non-symmetrical counter example to disprove this idea or to prove it ONLY happened with this symmetry. Not sure right now, how such a proof would go.

      You're making us think Katie!

      Delete