Tricolor Triangle

Generalize to subdividing an equilateral triangle of side $k$ (k a positive integer) into $k^2$ equilateral triangles of side $1$ . (The problem asks about the case $k=33$ .)

Observe that under the coloring rules, the colors of any two sides of a unit triangle uniquely determine the color of the remaining side. If the color of only one side is known, either of the other two sides can be given any color, and that forces the color of the third side.

For $k = 1$ , there are $3^2 = 9$ ways to color two sides any way you want, each leading to a unique coloring of the triangle.

So lets build up our size- $k$ triangle a row at a time. Take any coloring of a size- $k-1$ triangle, and add a row of unit triangles along the bottom. The bottom row of the $k-1$ -sized triangle gives us $k-1$ already-colored segments, joining $k$ vertices. The new row of triangles has two new line segments descending from each of those vertices. Starting from the left, color the first two however you want, and that uniquely colors two of the new triangles. Continue coloring the next uncolored descending edge, to uniquely color two new triangles, until you get to the last edge, which only determines the coloring of the one new triangle.

All in all, we've been able to freely choose the colors of $k+1$ new edges, and get a unique valid coloring of the rest.

Thus, for $k=2$ , we had $3^2$ ways to color the top triangle, and $3^3$ ways to extend that coloring to the second row, for a total of $3^2⋅3^3$ colorings.

For k=3, we can extend each of those in $3^4$ ways, to get $3^2⋅3^3⋅3^4$ colorings. And in general, for a triangle of side $k$ , we get $3^2⋅3^3⋅ ⋅⋅⋅ ⋅3^{k+1} = 3^{2+3+⋅⋅⋅+(k+1)} = 3^{k(k+3)/2}$ colorings.

For $k = 33$ , that's $3^{33⋅36/2} = 9^{33⋅9} = 9^297. log_9 (9^297) = 297$ .

Defining terms, assume the triangle to be pointing upwards. then the top unit triangle will belong to the first layer, the two up-pointing unit triangles below it belong to layer 2, and etc. The down-pointing triangles will belong to half layers. That is, the highest down-pointing triangle will belong to layer 1.5, then the two below will belong to layer 2.5, and so on.

First, let $f(n)$ be the number of colourings for an $n$ -layered triangle. $f(1)=9=3^2$ (RRR, RGB, RBG, BBB, BRG, BGR, GGG, GBR, GRB)

Now, consider $f(2)$ . The top triangle will have $9$ possibilities. The center triangle will then have 1 edge determined, leaving it with 3 possible colourations. Likewise, the triangles at the left and right of the 2nd layer will have 1 edge determined by the center triangle, so they will both have 3 possible colourations. Multiplying, we get $f(2)=3^5$

Next, consider $f(3)$ . Building upon the previous triangle, we add on the two triangles belonging to layer 2.5. These triangles will have an edge predetermined, so they each have 3 possibilities. Moving on to layer 3, we see that the two triangles at the sides are similar to the previous case, thus will have 3 possibilities each. The middle triangle, however, has 2 edges determined by the two triangles in layer 2.5. The final edge is then fixed for the middle triangle. (If the two edges have different colours, the last edge is coloured the remaining colour. Otherwise if the two edges have the same colour, then the last edge is also that colour) Thus, $f(3)=3^5\times3^2\times3^2=3^9$

From $f(4)$ onwards, it can be observed that $f(n)=f(n-1)\times3^{n+1}$ , as only the half-layered triangles and the cornermost triangles in the integral layers will affect the number of colourations. By expanding, we get $f(n)=3^{2n+\frac{n(n+1)}{2}}$ (Where $2n$ is the possible colourations of the side triangles and $\frac{n(n+1)}{2}$ is the possible colourations for the down pointing triangles)

$f(33)=3^{2\times33+\frac{33(34)}{2}}=3^{594}=N$ Thus, $\log_9N=297$

I worked my way through this outstanding problem by first experimenting for small values of n and then guessing a general formula. I then found a proof.

First of all, let n be the number of smaller equilateral triangles on the side. You get the following pattern

n=1, #ways= $3^2$

n=2, #ways= $3^5$

n=3, #ways= $3^9$

n=4, # ways= $3^{14}$

This led me to search for a reason why this pattern might be true in general.

In general, let $f(n)$ be the number of ways to colour the $n^2$ triangles. Then, to get $f(n+1)$ , we have the number of ways of colouring the top equilateral triangle with $n^2$ triangles, plus we have one more row of n+1 triangles.

Given the conditions in the question, we can colour the bottom edges any way we want, and can freely pick only one edge along the side. This then forces all the other colours in the new row.

So we have $f(n+1)=f(n)*3(n+2)$

and the formula $f(n)= 3 ^ {\frac{(n)(n+3)}{2}}$

evaluating for n=33, we get $3^{594}$

$log_9(3^{594})=297$

Let it be g(k) the answer for a triangle of side k If k>1, to paint the k figure, we can paint the k-1 figure, rows 1(upper) to k-1, of g(k-1) ways. Now, looking below: we can paint the k segments horizontal and the most left segment diagonal of 3^(k+1) ways, now each triangle below have a unique configuration, because the color of 2 sides determine the color of the third (it is determined the third segment of the most left triangle, now the same in the next, and so all). Hence g(k) = 3^(k+1)g(k-1). Inductively g(k) = 3^( k(k+3)/2 ), so g(33) = 3^(33 18), so floor(log_9(g(33))) = floor(33 9) = 297

We can see that there are 9 ways to color the top triangle, those are 3 different ways of coloring in similar color, and 3! different ways to color in different colors. Now we see how many ways we can color the triangles on the second row, or right below the top triangle. For every ways of coloring the top triangle, the upside down triangle right below has a single side color already chosen. From such restriction, there are three ways of coloring, coloring all the side the same way, or having the remaining two sides being colored by the two remaining color in two different orders. After coloring the upside down triangle, we see that the two triangles at the leftmost and rightmost is also restricted by the condition such that one of it's side is already colored. There are three ways to color them. Continuing to the next row, there are two upside down triangle with three ways to color each and two triangles at the leftmost and the rightmost of the row with three ways to color each. The triangle between the upside down triangle has two sides colored, so there is exactly a single way to color it. We don't need to consider them for the calculation. Continuing with this pattern, the ways to color row number n (other than topmost row) is 3^(numbers of upside down triangle+2) = 3^((n-1)+2) = 3^(n+1) So the way to color the full triangle is 9 X 3^3 X 3^4 X ......X 3^34 = 3^(2+3+4+......+34) = 3^594 (log3^594)/(log9) = 297

We’ll start by coloring a $1\times1$ triangle. We’ll use what we establish in the $1\times1$ for the rest of our problem. And to be consistent, draw the triangle with a base parallel to the ground.

Let’s choose the color of the first side. There are $3$ ways of doing it. (Since the problem says that rotations and reflections are distinct, we don’t have to worry about overcounting.) After we choose the first side, we can make the sides all different colors, or all the same.

1. The sides are all different colors. There are 2 ways of doing this, since the color of the first side is already fixed.
2. The sides are all the same color. There is 1 way of doing this if the color of the first side is already fixed.

This gives $2+1=3$ ways to color a $1\times1$ triangle if we know the color of one of the sides. Since the first side had 3 choices of color, this gives a total of $3*3=9$ ways to color a $1\times1$ triangle.

On to a $2\times2$ . Draw it with one of the bases parallel to the ground. We know the top triangle has 9 configurations. The triangle directly below has 3 configurations, because its top side already had a fixed color. The triangles adjacent to this also have 3 configurations, because one of their sides was fixed by the configuration of the middle triangle. So on this $2\times2$ , we have to multiply $9$ by $3^3$ for the bottom row, which gives $3^{2+3}$ ways to configure a $2\times2$ triangle.

Similarly for a $3\times3$ , the two triangles in the bottom row with bases parallel to the ground have 3 configurations from the triangles in row 2, so we multiply the configurations of a $2\times2$ by $3^2$ . The triangles on the ends have 3 configurations from the triangles we just colored, so we again multiply by $3^2$ . If the colors were different on the inside triangle’s two slant sides, we would have just one way to color the remaining side, and if the colors were the same on the inside two slant sides, we would also have just one way to color the remaining side. Either way, we will have one way to color the remaining side. So for a $3\times3$ , we have to multiply the configurations of a $2\times2$ by $3^2\times3^2=3^4$ (for the bottom row) which gives $3^{2+3+4}$ .

Did you see the pattern yet?

For a $n \times n$ triangle, the number of colorings is $3^{2+3+4+\cdots+(n+1)}$ .

So for a $33\times33$ triangle, the number of colorings is $3^{2+3+4+\cdots+34}$ . The exponent is the sum of an arithmetic sequence with first term 2, last term 34, and common difference 1. The sum of this sequence is $\frac{(2+34)(33)}{2}=594$ .

So there are $3^{594}$ ways to color a $33\times33$ triangle. $\text{log}_{9}3^{594}=\text{log}_{9}9^{\frac{594}{2}}=\text{log}_{9}9^{297}=297$ . $\lfloor{297}\rfloor=\boxed{297}$ .

Be a n = number of ways to color a triangle of side n respecting the conditions of the utterance. As seen, a 1 = 9.

Note that a triangle of side n is nothing more than a triangle of side n-1 added (n-1)+n = 2n-1 triangles of side 1, arranged in a unique manner. Note that this "natural disposition" n-1 leaves triangles one side in contact with the larger triangle side (n-1), which can be colored a_ {n-1} distinct ways. Note also that these coloring n-1 smaller triangles, the color of the remaining n can be uniquely except 2 triangles, the triangles having vertices coincide with the vertices of the triangle next higher n: for these we only had one color well defined and, by (o), we have 3 * 3 = 3^2 ways to color them (oo).

Let's count how many ways we can then color these n-1 triangles. As they only have vertices in common, the coloring of them is independent and so we look at just one of them.

(o) As we have seen, one of the smaller triangle n-1 already has a colorful side and we have two cases to consider:

• The triangle will be colored one color, as already colored the one hand, this can be done in only one way.

• The triangle will be colored with three distinct colors: as one side is already colored, we have 2 * 1 = 2 ways to do this.

Soon each small triangle can be colored in three modes, first by multiplying the n-1 smaller triangles can be colored 3 ^ {n-1} ways. At first multiplier and (oo), we conclude that a n = 3 ^2* 3 ^ {n-1}a {n-1}= 3^ {n +1} * a_ {n-1}

where then a n = 3 ^ {n+1}*3 ^ {n} *...*3^3*a 1 = 3 ^ {P}

Where P = (n+1)+(n)+(n-1)+...+(3)+(2) = (n+1)*(n+2) / 2 -1.

For n = 33, we have P = 34*35/2-1 = 594, where a_ {33} =3^{594} = 9 ^ {247}, where

[log_ {9} N] = [log_ {9} a_ {33}] = [9 log_ {9} ^ {247}] = [247] = 247

First, we shall focus on the top unit triangle in the corner of this lattice of triangles. This triangle's sides could either all be of the same colour, or they could all be of different colours. This therefore gives us a total of $3+3! = 9$ ways to colour the top triangle.

Moving on to the unit triangle directly below and adjacent to the top triangle (which will be referred to as $X$ ), we assume that the side that it shares with the top triangle is fixed. (This will not affect the final answer, as we will be multiplying the number of configurations of all the unit triangles together.) Thus, either the other two sides of said triangle is the same colour as the shared side or they are of different colours, giving $1+2 = 3$ ways to colour this triangle.

Next, for the two triangles on either side of $X$ , we assume once again that the side that they share with $X$ is fixed and find out that the number of ways that they can be coloured is $1+2 = 3$ ways, similarly deduced like $X$ . If we were to calculate the number of ways to colour all the triangles along the side of the large triangle, we find that they all have the same number of configurations (3 ways). In general, triangles with 1 fixed, shared side will have only 3 ways to be coloured.

Now, if we look at 2 triangles along the sides, concentrating on the triangle that shares sides with both these triangles, we find that this particular triangle can also have 3 possible colour configurations.

Finally, numbering the 33 rows of unit triangles of the large triangle 1 to 33, where the top triangle is in row 1, the triangle right in the middle of row 3 (triangle $Y$ ) will only have 1 possible configuration, since the two triangles beside it are already confirmed to have 3 configurations, the sides that they share with $Y$ can be considered to be fixed, thus only giving $Y$ one possible colour for its remaining side. This is the same for any triangle that already has two fixed sides.

Thus, if this process is carried out for the first 3 layers of the large triangle, finding out the possible colour configurations for each unit triangle, a pattern emerges.

We find that the top triangle has 9 configurations, triangle $X$ and the two rows of triangles along the sides (excluding the base of the large triangle) having 3 configurations. In remaining triangles from row 3 to 33, it is clear that every triangle that has a vertex pointing up can only have 1 possible configuration because 2 of their sides are already fixed by surrounding triangles. Lastly, the remaining triangles that have a vertex pointing downwards have 3 possible colour configurations.

Hence,

Number of triangles with 9 colour configurations $= 1$

Number of triangles with 1 colour configuration $= \frac {(31)(31+1)}{2} = 496$

Number of triangles with 3 colour configurations $= 33^2 - 496 - 1 = 592$

Therefore, we can find $N$ by multiplying all the possible colour configurations of all the unit triangles together:

$N = 9 \times 3^{592} \times 1^{496} = 3^{594}$

Finally, we can calculate the value of $\lfloor {\log_9 N} \rfloor$ .

$\lfloor \log_9 N \rfloor = \frac {\log_3 {3^{594}}}{\log_3 9}$

$= \frac {594}{2}$

$= 297$