Triangle

[Lado]

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, or green (or any three colors of your choosing) 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) PROVE your answer.

[CaptainEd]

Answer and proof:

First, think of the colors as ternary numbers, 0, 1 and 2

The rules are

00->0

01->2

02->1, 

11->1, 

12->0, 

22->2

Notice that this function simplifies to
XY->(3-X-Y)mod3 = ( -(X+Y)) mod3

Specific case: XX-> -Xmod3

Let’s name the blocks A through J, and use a non-standard notation:

AB-CD means (A+B-(C+D))mod3

The blocks are separated by semicolons.

(1) A;B;C;D;E;F;G;H;I;J

(2) -AB;-BC;-CD;-DE;-EF;-FG;-GH;-HI;-IJ

(3) AC-B;BD-C;CE-D;DF-E;EG-F;FH-I;GI-J;HJ-I

(4) -AD;-BE;-CF;-DG;-EH;-FI;-GJ

(5) ABDE;BCEF;CDFG;DEGH;EFHI;FGIJ

(6) BE-ACDF;CF-BDEG;DG-CEFH;EH-DFGI;FI-EGHJ

(7) AG-D;BH-E;CI-F;DJ-G

(8) DE-ABGH;EF-BCHI;FG-CDIJ

(9) ACEGI-BDFH;BDFHJ-CEGI

(10) -AJ

So the method is: discard the 8 middle blocks, and calculate using the original rule on the first and last blocks.

[CaptainEd]

Sorry, typographical error in line (3)

Should end: ...EG-F;FH-G;GI-H;HJ-I

[EventHorizon]

Beat me to it, kudos CaptainEd.  I guessed the solution and came up with a proof while trying to get to sleep last night.  The first step was inelegant, so I was going to work on it a bit before posting.

Spoiler

First, show the bottom block of all triangles of height 4 can be found by using the consecutive block coloring rule on the first and last block.

I brute forced it, but reduced the needed examples by relabeling colors and flipping order.  This was the part that needed to be done more elegantly.  CaptainEd's proof does this part well.

 

I may have added a step showing that blocks outside of sub-triangles don't influence colors inside the sub-triangles.  Fairly obvious.

 

Then, notice that the 10 block triangle can be seen as 3 height 4 sub-triangles, 2 height 4 sub-triangles under that, and a final height 4 sub-triangle... all with overlapping corner blocks.  This new formation is equivalent to another triangle of height 4 because the first step of the proof showed that for triangles of height 4 you only needed to do the coloring rule on first and last blocks.  Using the first step of the proof again, the last block of the 10 block triangle is just the coloring rule on the first and last blocks of the height 10 triangle.

 

Using this method, you can see that for any triangle of height 1+3^n for n=0 to infinity, the last block is simply the coloring rule on the first and last blocks.

 

I thought it could be interesting to try to find out the minimum number of applications of the coloring rule you would need to do to determine the color of any given block from a triangle of height X based on its height, but haven't thought too much about it.  It could be an interesting number sequence. 0,1,3,6,1,3...

This problem reminded me a lot of

Spoiler

The creation of Sierpinski's Triangle by starting with a 1 with infinite 0's on either side, and the next row is made by exclusive or of the two numbers above.

1

11

101

1111

10001

110011

1010101

11111111

etc

 

[CaptainEd]

Event Horizon, you have shed a lot of light on this puzzle! Your observations about the 4-triangle and  1+ 3^n are quite surprising and pleasing. It is I who brute forced it; you actually came to a deeper understanding. I’ll send you kudos as well.

[intotheravine]

Spoiler

Answer: The last block can be determined by applying the rules to the first and last blocks of the first row.

I wrote a little app simulating the problem and observed the results. I replaced the colors with the numbers 1, 2 and 3 and observed several cases by randomizing the values of the first row. The pattern soon emerged.