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.
Let's take a look first at Pascal's Funnel: A vector of N arbitrary numbers in the top row P(N,1), P(N,2), ... P(N,N); together with the rule for constructing lower rows
P(N-K, M) = P(N-K+1, M) + P(N-K+1, M+1)
For a given L, P(L, R) is defined for the R=1, ..,L
Here is an example of Pascal's Funnel for N=4:
6 -8 1 4
-2 -7 5
-9 -2
-11
The value at the bottom of Pascal's Funnel, P(1,1) is given in terms fo the top row by the formula:
P(1,1) = Sum_J C(N-1,J-1) * P(N, J) with J ranging over the values 1 thru N
Here C(A,B) = A!/(B!(A-B)!) is the combination of A over B.
In the example above
P(1,1) = 1(6) + 3(-8) + 3(1) + 1(4) = 6 - 24 + 3 + 4 = -11
Why does this work? Because the combinatorics of Pascal's Funnel are the same as the combinatorics of the binomial expansion. Prove it using induction and the identity:
C(A,B) = C(A-1, B) + C(A-1, B-1)
Now we are ready to take on this problem. But, instead of colours it is useful to have the top row populated by integers 0, 1 and 2 (each assigned to a distinct colour). This time the rule for populating a lower rule is
P(L,M) = 2*( P(L+1,M) + P(L+1,M-1) ) mod 3
Using this rule, the daughter cell calculated from two parent cells is as follows:
D(0,0) = 0 D(1,1) = 1 D(2,2) = 2 D(0,1) = 2 D(1,2) = 0 D(2,0) = 1
and D(A,B) = D(B,A)
The formula from Pascal's Funnel can easily be adapted to give
P(1,1) = 2^(N-1) ( P(N,1) + NP(N,2) + N(N-1)/2 P(N,3) ...) mod 3
This can be simplified. Since AB mod C = (A mod C)(B mod C) and 2 = -1 mod 3, we get:
P(1,1) = (-1)^(N-1) [ P(N,1) + NP(N,2) + N(N-1)/2 P(N,3) ...] mod 3
Here the formula applied to Jer's top row: RBYYB.
We adapt the arbtrary convention R->0, B->1, Y->2, so the top row is 01221 and we have N = 5, so the bottom term is
(-1)^4 (0 + 4*1 + 6*2 + 4*2 + 1*1) mod 3 = 25 mod 3 = 1 mod 3 = 1 -> B
There may be a pattern to the the combinatorials, mod 3; thus leading to further simplification. But that may be taking things too far for what I can write in this box.
|
|
Posted by FrankM
on 2020-08-26 08:28:03 |
Complete formula
