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.
Submitted without proof, as what I've come up with is really more observation than demonstration.
I modeled the three colors with 0,1,2 and noticed that for every pair (a,b) with resultant entry c, 3 divides (a+b+c). So I tried a few calculations with the string abcdef... Looking at the first entry only gave:
Step 1 (a+b)
Step 2 (a+2b+c)
Step 3 (a+3b+3c+d)
Step 4 (a+4b+6c+4d+e)
Step 5 (a+5b+10c+10d+5e+f)
I know binomial coefficients when I see them, and since the first entry eventually becomes the final entry, the plan is clear how to evaluate a string with N entries.
1) find the coefficients of (x+y)^(N-1)
2) sum the products of the kth string value and the kth coefficient
3) subtract the result from the smallest multiple of 3 that is greater
|
|
Posted by xdog
on 2018-12-17 20:03:48 |
proposed solution
