Jukka-Pekka Ikaheimonen, michael reid, Dave Tuller, Martin I Eiger, David Shallcross, and Joseph DeVincentis sent solutions.

The solution comes after realizing that all diagonals are palindromes.

Here are a couple proofs:

Theorem: If you start with a 1 x n strip, then the process will

terminate, at the latest, when the nth strip is placed.

Proof: First, notice that this procedure gives a unique pattern

determined by the initial 1 x n block. Therefore, it suffices to

determine an n x n square such that for each unit square, an even number

of its neighbors is a different color and that the bottom row is the

given 1 x n block. To this end, let the colors be denoted 0 and 1.
We

label the n x n square with coordinates along the x and y directions
0,

1, 2, ..., k = n-1 (this k is for convenience only). Let the color

sequence of the 1 x n block be a_0, a_1, ..., a_k. Now define c_{x,y}
=

the color of the square with coordinates x and y = a_{y-x}+...+a_{y+x}

(mod 2) whenever x <= y <= k-x. The remainder of the colors can
be

determined by c_{x,y}=c_{y,x}=c_{k-y,k-x}. It is simple to check that

this colored square satisfies the required conditions. Q.E.D.

Consider a starting configuration that decomposes into subsequences,

each of length K. The first, third, fifth, etc., subsequences
are all

A1,A2,A3,...,AK. The second, fourth, sixth, etc., subsequences
are

all AK,A(K-1),A(K-2),...,A1. It doesn't matter whether the number
of

subsequences (N/K) is even or odd, as long as they alternate.

David asserts that all such starting configurations converge in K

rows. I believe the argument is that each subsequence grows

(vertically) independently, and adjacent cells across the boundaries

between subsequences will always be the same color.

Moreover, I believe that he argued that all starting configurations

that converge in fewer than N rows have this form. The logic
is that

if you have an N*K array of blocks where each cell has an even number

of oppositely colored neighbors, then you can rotate it 90 degrees,

strip off the top (N-K) rows (since we have already shown that K cells

will converge in K rows), and then rotate it back.

the game always terminates after at most n-1 rows have been
added

to the original. in fact, the array you build up is symmetric

over the diagonal line x = y (also over the other diagonal).

we prove this by induction.

proof. when we add square (i, j) there are three cases.

i >= j. then square
(j, i) hasn't been filled yet,

so there is no requirement.

i = j - 1. so we're
filling square (i, i+1) in such a

way that (*)
holds for square (i, i). its other neighbors

are (i-1, i), (i, i-1) and
(i+1, i). the first two have

the same color (or are empty,
if i = 1) by the symmetry

condition (and implicit
induction hypothesis). so square

(i, i+1) matches (i+1, i)
in order for the number of blue

neighbors to be even.

i < j - 1. now
we're filling square (i, j) so that (*)

holds for square (i, j-1).
its other neighbors are

(i, j-2), (i-1, j-1) and
(i+1, j-1), which match

(j-2, i), (j-1, i-1) and
(j-1, i+1), respectively.

since (*) holds for square
(j-1, i) which matches (i, j-1),

we see that (i, j) must
also match (j, i).

this completes the proof.

now we see that after n-1 rows are added to the initial
one, we

have a square which is symmetric over the line x = y .
in particular,

condition (*) is satisfied for all squares (i, n) , 1 <= i
< n,

since the condition is satisfied for square (n, i). condition
(*)

also hold for square (n, n), since its two neighbors, (n-1, n) and

(n, n-1) have the same color. so the game stops here, although
perhaps

it could have terminated earlier.

Sometimes these things just come to you and sometimes they take

a long time. Anyway, there is no such coloring. Suppose there is,

for some finite length of strips n. The colors on one strip only depend

on the colors on the two strips immediately before that one. Since

there are only 2^n possible sequences of colors on a strip, there are at

most 2^2n sequences of colors on 2 consecutive strips, so after at most 2^2n

+ 1 strips, the pattern of colors on a pair of consecutive

strips must repeat, and once it does, the entire cycle of strips between the

repeating ones will repeat forever. Now, in this

semi-infinite row of strips, the (*) condition is true for every square.

Given this, and starting at some strip in the repeating sequence, we

can work backwards, figuring what every strip must be based on the two

strips which *follow* it, because those two strips determine a unique strip

which could have occurred before them, in exactly the same way any two

strips uniquely determine the one which follows

them, in the original procedure.

Eventually, we will reach the first two strips. Our calculation
*must*

produce the sequence on the first two strips, due to the uniqueness
I

described above. However, also due to this uniqueness, these
first

two strips must appear in the repeating sequence (the sequence repeats
when

run backwards, too). Now, what strip must be the one

which appears before the first strip, where the first two strips appear
in

the repeating sequence? Since this strip works at the end of
the

sequence, it must be another identical strip (no squares of opposite

color next to any of the squares in the first strip, since none are

needed), and the strip before that one is a repeat of the second strip

(since the duplicate first strip has no contribution of opposite-colored

squares from the first strip, it needs the same strip as our original
second

strip to meet the (*) condition). However, if the repeating sequence

contained such a sequence (which at some point contains

a duplicate second strip followed by a duplicate first strip), it would

have ended there, because we know that pattern of strips meets (*).

Thus, our initial assumption that we can create such an infinite chain

must be incorrect.