Problem

Source: 2024 Argentina L3 P6

Tags: combinatorics



An equilateral triangle with integer side length $n$ is subdivided into smaller equilateral triangles of side length $1$ by drawing lines parallel to its sides, as shown in the figure for $n = 4$. [asy][asy] size(5cm); // Function to draw an equilateral triangle with subdivisions and mark vertices void drawTriangleWithDots(pair A, pair B, pair C, int n) { real step = 1.0 / n; // Draw horizontal lines for (int i = 0; i <= n; ++i) { pair start = A + i * step * (C - A); pair end = start + i * step * (B - C); draw(start -- end, gray(0.5)); } // Draw left-leaning diagonal lines for (int i = 0; i <= n; ++i) { pair start = A + i * step * (B - A); pair end = start + (n - i) * step * (C - A); draw(start -- end, gray(0.5)); } // Draw right-leaning diagonal lines for (int i = 0; i <= n; ++i) { pair start = B + i * step * (C - B); pair end = start + (n - i) * step * (A - B); draw(start -- end, gray(0.5)); } // Mark dots at all vertices for (int i = 0; i <= n; ++i) { for (int j = 0; j <= i; ++j) { pair vertex = A + i * step * (C - A) + j * step * (B - C); dot(vertex, black); } } // Draw the outer triangle draw(A -- B -- C -- cycle, black+linewidth(1)); } // Main triangle vertices pair A = (0, 0); pair B = (4, 0); pair C = (2, 3.464); // Height = sqrt(3)/2 * side length // Subdivisions int n = 4; // Draw the subdivided equilateral triangle with dots drawTriangleWithDots(A, B, C, n); [/asy][/asy] Consider the set $A$ consisting of all points that are vertices of any of these smaller triangles. A subtriangle is defined as any equilateral triangle whose three vertices belong to the set $A$ and whose three sides lie along the lines of the initial subdivision. We wish to color all points in $A$ either red or blue such that no subtriangle has all three vertices of the same color. Let $C(n)$ denote the number of such valid colorings for each positive integer $n$. Calculate, in terms of $n$, the value of $C(n)$.