Painting Blocks

[BMAD]

Form a “triangle” with 10 blocks in its top row, 9 blocks in the next row, etc., until the bottom row has one block. Each

row is centered below the row above it. Color the blocks in the top row red, white and blue in any way. Use these two

rules to color the remaining rows of the triangle:

 

• If two consecutive blocks in a row have the same color, the block between them in the row below has the same color.

• If two consecutive blocks in a row have different colors,the block between them in the row below has the third color.

 

Tell how you can always predict the color of the bottom block after seeing only the top row (and not constructing the intermediate rows).

[gavinksong]

I'll refer to the three colors: as R, B, W.

 

Notice that for two consecutive blocks in a row, given the color of the first block in the series, the color of their child is a function of the color of the second block in the series. That is, it is a function which maps {R,W,B} to {R,W,B}. In particular, it maps the color of the first block to itself and swaps around the other two colors. For example, if the first block is red, then R->R, W->B, and B->W.

 

To make a long story short, for more than two consecutive blocks in a row, the color of their bottommost child can be seen as a composition of functions. For example, if the first two blocks are red and blue, then we must compose the function that maps R->R, W->B and B->W with the function that maps R->W, W->R, and B->B.

 

To demonstrate the solution, consider the initial row of 10 blocks: RWBBRWRRWB.

We can now apply well-known algebra tricks to reduce this row of blocks to another that would produce a bottommost child with the same color. Namely, since composition is commutative, we can resolve certain easy compositions first, such as RR, WW, or BB which result in the identity function.

RW(BB)RW(RR)WB == RWR(WW)B == RWRB

Now all that is left is to evaluate the composition RWR. For those of you familiar with algebra, you might notice this fits the template of a similarity transformation, RWR^-1, since R is its own inverse. The equivalent function is similar to W, but under a "change of basis" function R, so instead of W mapping to itself, B does. Thus, RWRB == BB. Of course, we could have also composed the function by hand. Finally, B maps B to itself, so the color of the bottommost block is B.

[bonanova]

@gavinksong, I get W for your example.

 

You can just look at the colors of the two end blocks, ignoring the middle eight blocks.

Using the rule in the OP, the two end blocks give the color of the bottom block.

 

This works not only for ten rows, but any time the number of rows above the bottom block is a power of 3:

That is, it works for any "triangle" that has 1+3ⁿ = 2, 4, 10, 28, 82, 244, ... rows.

[bonanova]

First off, we recognize that the rule given in the OP is comprehensive analysis of a 2-high triangle.

Next, we recognize that the "vertex rule" is followed by the vertices of 4-high triangles.

This could be proved by formalizing the OP rule and turning it loose on a general 4-high triangle.

Fortunately, there aren't that many 4-high color patterns, and we can just work them all out.

See the next spoiler.

WOLOG let the first block have color a, then look at the other three blocks:

There are 14 color patterns for a 4-high triangle's top row.

 

a a a a -- All one color

 

a a a b -- a plus one other color, say b
a a b a
a b a a
a a b b
a b a b
a b b a

 

a b b b -- All one other color, say b.

 

a b b c -- Just the other two colors with say b more numerous than c
a b c b
a c b b

 

a a b c -- All three colors
a b a c
a b c a

 

Mirror images and color permutations give all cases from these 14 patterns, all of which can easily be verified.

 

Here are a few 4-high cases.

 

a a a a    a a a b    a b a b    a b c a    a b b c
 a a a      a a c      c c c      c a b      c b a
  a a        a b        c c        b c        a c
   a          c          c          a          b

 

The underlined colors show that 4-high triangles obey the "vertex rule."

 

Do 7-high triangles obey the vertex rule?
Not in general:

 

a b b c c a b      a a b b c b a
 c b a c b c        a c b a a c
  a c b a a          b a c a b
   b a c a            c b b c
    c b b              a b a
     a b                c c
      c                  c

 

The vertex rule is obeyed by the first triangle above, where the top-row end colors are different; but not by the second, where they are the same.

 

Do 10-high triangles obey the vertex rule?

 

The OP is actually a vertex rule for triangles that have 1+3⁰ or 2 rows.

We've seen the vertex rule is followed for the next case of 1+3¹ or 4 rows.

We see in this section that the case of 1+3² = 10 rows reduces to the 4-high case, and so itself obeys the vertex rule.

This gives the process for proving by induction that the vertex rule is followed by all triangles having 1+3ⁿ = 2, 4, 10, 28, 82, 244, ... rows.

 

Here are two 10-high triangles.

Note they each have six embedded 4-high "vertex" triangles.

 

a b c b c a a c b b   9   c b b a c b a a c a
 c a a a b a b a b    8    a b c b a c a b b
  b a a c c c c c     7     c a a c b b c b
   c a b c c c c      6      b a b a b a a
    b c a c c c       5       c c c c c a
     a b b c c        4        c c c c b
      c b a c         3         c c c a
       a c b          2          c c b
        b a           1           c a
         c            0            b

 

The underlined blocks are the vertices of embedded 4-high triangles.

These vertices can thus be extracted to form a single 4-high triangle.

 

      a b a b         3         c a a a
       c c c          2          b a a
        c c           1           c a
         c            0            b

 

We've seen that 4-high triangles obey the vertex rule.

Their vertices can be extracted to form 2-high triangles.

 

Note the remaining blocks are precisely the vertices of the 10-high triangle.

Thus the 10-high triangle obeys the vertex rule.

 

        a b           1           c a
         c            0            b

 

In general, a triangle having 1+3ⁿ rows follows the vertex rule.

[gavinksong]

You're right, bonanova.

I should've known: my solution did seem a bit complicated. :S