Begin with a finite sequence of blocks in a row, each in one of 3 colors: red, blue, yellow.
Below each pair of neighboring blocks place a new block with the color rule: If the blocks are the same color use that color but if they are different use the third color.
Example:
r b y y b
y r y r
b b b
b b
b
How can the color of the last block be easily predicted from the top row?
Note: I don't know the full answer but can solve special cases.
(Imagine numbers such as 1,2,3 or better -1,0,1 instead of colors)
Two ideas - the first is very abstruse.
1) Convolution integrals: Consider each line as a discrete function (perhaps of the same length as padded with trailing 0's).
Each successive line is the previous line convolved with the same kernel, not unlike a running weighted mean that takes 2 elements at a time. Here * represents convolution (done over an integral or a summation). Thus, we have an integral equation: a1 = a0 * s, where a0 is the first line, s is the convolution kernel, and a1 is the second line.
One can represent convolution with "*", and multiplication of x and y as xy. Further, X is the Fourier Transform "F[.]" of x, and x is the inverse transform F^-1[.] of X, and {X} is the complex conjugate of X. The convolution theorem says:
x * y = F^-1 [{X}Y]
In words - One can convolve two functions by taking the transform of each, multiplying these (after taking the complex conjugate of the first) and then take the inverse transform of the product function.
So, what the blazes does all of this have to do with this problem? The method is a way of changing a convolution into a multiplication. For example, rather than pass a running mean (boxcar) over a function, one can multiply its FT by a sinc function and then take the inverse transform of the product function, because the sinc function is the FT of a boxcar function. This works with discrete functions and DFTs.
So if you have x*y you may be able to get there by going for {X}Y. However, what we have here is actually ((((x*y)*y)*y)*y). I am still thinking about how to express y (with dirac delta functions?) and would be the form of a FT a recursive series of convolutions...
2) This idea is much more down to earth:
When you multiply matrices, the matrix dimensions follow rules such as:
[1 x n] x [n x n] = [1 x n]
So, consider the input something like:
a0 = [y b r b b y r] = [0 1 -1 1 1 0 -1]
You would want to find a 7x7 matrix S that gave
a1 = a0 x S
[1 -1 0 1 -1 1 0] = [0 -1 -1 1 1 0 -1 ] x S
I have not found one such S. But, if you had one (spinners?) along with corresponding numerical choices for (r y b), you could use the associative property of matrix multiplication to great advantage:
a1 = a0 x S
a2 = a1 x S = (a0 x S) x S = a0 x (S x S). So, for example,
a6 = a0 x S^7 = where S is multiplied by itself 7 times; S^7 is still a 7x7 matrix.
Find an appropriate choice of r,y,b along with a S that works, and the problem is solved.
A simpler first step is this: Can the 2x2 case be found?
Find appropriate a, b, c (all different) and d_n, a padding number or numbers and q r s t such that
q r
s t
is a 2x2 matrix called S, where
[a a] x S = [a d_i]
etc.
[a b] x S = [c d_i]
[b a] x S = [c d_j]
etc.
Edited on December 15, 2018, 4:12 am
just a couple of off-the-wall ideas
