All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers > Sequences
Colored triangle (Posted on 2018-12-14) Difficulty: 4 of 5
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.

No Solution Yet Submitted by Jer    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Complete formula Comment 10 of 10 |
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information