Counting Triangles II
A triangle is split into n2 smaller triangles by evenly spaced lines parallel to its sides. Two small triangles that share a side are said to be adjacent. The task is to count the small triangles by first selecting one of them and then moving from a triangle to an adjacent one without stepping twice into the same triangle. Can you count all n2 triangles in this manner? If not, how many can you?
|What if applet does not run?|
(Clicking on triangles may help your counting.)
It's not possible to count all the small triangles. The best one can do is to count
n2 - n + 1
of them, and this is why.
The small triangles can be painted in the "checkerboard" pattern so that any two adjacent triangles have different colors. There are n(n+1)/2 triangles (painted red) and n(n-1)/2 (orange) triangles. Every time one counts a new triangle, the count moves from a triangle of one color to a triangle of a different color. Thus one cannot count more than twice the number of orange triangles plus 1, provided the first triangle is red. Which gives, as a maximum,
n(n-1)/2 + n(n-1)/2 + 1 = n2 - n + 1,
as required. That is, we certainly can't do better than (1). Yet, we have not proved that the number is achievable. In practical terms, the problem remains: can you construct a chain of adjacent triangles of length given in (1)? (Here's the answer.)
Yes, it is not difficult to construct a chain of adjacent triangles of length
In each layer, all triangles but either the leftmost or the rightmost form a parallelogram which is a chain of triangles with the exit and entry points at the opposite corners. Thus in each layer there are two possible parallelograms. The parallelograms can be now stacked on top of each other continuously so that the exit edge of a layer coincides with the entry edge of the next layer above. In all, the chain will include
2(n-1) + 2(n-2) + ... + 2 + 1 = n(n-1) + 1
triangles. Exactly as in (1).
Nathan Bowler offers a proof by induction:
Base case: For n = 1, the triangle itself is a chain of length
Induction step: Pick a side adjacent to the given corner. The triangles with at least one vertex on that side form a chain of length
Of course, this proof does not give an explicit construction, but it suggests two reasonably pleasant ones: a zigzag and a spiral.
Note: the discrepancy between the two kinds of cells in the general partition of a triangle into smaller ones, shows up in a different problem.