Each side of an equilateral triangle is divided into $n$ equal parts. Lines parallel to the sides of the triangle are drawn through these points, dividing the triangle into $n^{2}$ smaller triangles. We say that a sequence of distinct triangles is a chain if successive triangles share a common side. What is the largest possible number of triangles in a chain?
Solution

The answer is $n^{2}-n+1$ and a chain with this number of triangles is shown below. To show that this number is the maximum, color the triangles alternately with two colors as also indicated in the figure below. There are $n$ more white triangles than gray ones. Since the triangles in the chain are alternately colored, there can be at most one more white triangle than a gray one. Therefore, at least $n-1$ white triangles do not belong to the chain.

![](https://cdn.mathpix.com/cropped/2024_05_01_82072e76ed187b592b1cg-44.jpg?height=346&width=402&top_left_y=237&top_left_x=698)