Counting Triangles II

A triangle is split into n² 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 n² triangles in this manner? If not, how many can you?

---

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

---

What if applet does not run?

(Clicking on triangles may help your counting.)

Explanation

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

It's not possible to count all the small triangles. The best one can do is to count

(1)

n² - 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 = n² - 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

1. V. V. Prasolov, Problems in Planimetry, v 2, Nauka, Moscow, 1986, in Russian

Related material Read more...
	Counting: The Beginning of Mathematics
	Children's Counting Blocks Are Available
	The Idea of Counting
	Tribute to Invariance
	Dollars in Pockets
	Partitioning a Circle
	Counting Triangles
	100 Grasshoppers on a Triangular Board

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Yes, it is not difficult to construct a chain of adjacent triangles of length n² - 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 = 1² - 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)² - (n-1) + 1 triangles giving a total length of n² - 2n + 1 - n + 1 + 1 + 2n - 2 = n² - 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|

Copyright © 1996-2018 Alexander Bogomolny