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?
(Clicking on triangles may help your counting.)
Explanation
|Activities|
|Contact|
|Front page|
|Contents|
|Algebra|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
It's not possible to count all the small triangles. The best one can do is to count
of them, and this is why. (Press the "Show hint" button.)
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.)
Reference
- V. V. Prasolov, Problems in Planimetry, v 2, Nauka, Moscow, 1986, in Russian
|Activities|
|Contact|
|Front page|
|Contents|
|Algebra|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
Yes, it is not difficult to construct a chain of adjacent triangles of length n2 - n + 1. Think of the partition of the big triangle into the smaller once as being composed of (horizontal) layers. The lowest layer contains 2n-1 triangle, the next one 2n-3, ..., and the very last contains 1 (top) triangle.
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 1 = 12 - 1 + 1.
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 2n - 1. Take all the elements of that chain except the final one. The triangles not in that chain form a triangle of side n-1, of which you are now adjacent to the corner. By the induction hypothesis, then, we may extend the chain by a further (n-1)2 - (n-1) + 1 triangles giving a total length of n2 - 2n + 1 - n + 1 + 1 + 2n - 2 = n2 - n + 1.
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.
|Activities|
|Contact|
|Front page|
|Contents|
|Algebra|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
| 
