A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.
Mathematics Problem, #155
We can represent a triangle with sides of length a, b, c by the ordered triple (a, b, c). Changing the order of the sides doesn’t change the triangle, so (a, b, c), (b, a, c), (b, c, a), (c, b, a), (c, a, b), and (a, c, b) all represent the same triangle. To avoid confusion, let’s agree to write (a, b, c) with a < b < c. We say that a triangle <I (a, b, c) is integral if a, b, and c are integers. How many integral triangles are there with longest side less than or equal to 100 ?
Yet Another Mathblog 
87125?
Correct.
Just curious, how did you solve it?
It’s hard to explain in text. I haven’t done math since high school (6 years) and I’m a very visual thinker.. I used a lot of scratch paper.
I knew A+B>C, A+C>B, C+B>A and, after thinking about it for a bit, I knew there would be a LOT of triangles. So I needed to find some sort of pattern/rule that would determine how many triangles there are. I started by systematically generating & organizing possible triangles on paper with a branching tree. I did this for a little bit, then started looking for patterns.
My system for generating triangles had three rule:
Rule 1: (Trunk) The trunk of the tree is made up of nodes of all the equilaterals: (1,1,1) (2,2,2) (3,3,3) … (100, 100, 100).
Rule 2: (Limb nodes) Take any node, Update the value of A to A-1. If A+B>C, then grow the limb node (down)
Examples: (1,1,1) can’t grow a longer limb because 0+1 is not greater than 1.
(2,2,2) can grow one limb node: (1,2,2).
(3,3,3) can grow 2 limb nodes: (2,3,3) and (1,3,3).
(4,4,4) can grow 3 limb nodes.
(100,100,100) can grow 99 limb nodes. -> (1, 100, 100)
Rule 3: (Branch nodes) Update the value of B to B-1. If A+B>C, then grown a branch node (to the right)
Examples: The limb nodes of (1,1,1) and (2,2,2) have no branches.
(2,3,3) however has one branch node: (2,2,3).
(4,5,5) produces (4,4,5)
(3,5,5) produces (3,4,5) that node produces (3,3,5)
The rule in action:
(1,1,1) (2,2,2) (3,3,3) (4,4,4) (5,5,5)
(1,2,2) (2,3,3) (2,2,3) (3,4,4) (3,3,4) (4,5,5) (4,4,5)
(1,3,3) (2,4,4) (2,3,4) (3,5,5) (3,4,5) (3,3,5)
(1,4,4) (2,5,5) (2,4,5)
(1,5,5)
— — —equilaterals— — —>
|
|
| —(branch nodes)—>
(limb nodes) —(branch nodes)—>
|—(branch nodes)—>
|
|
V
The process produces an interesting pattern. Each equilateral triangle of side length (s) produces a pyramid of nodes with a base of limb nodes equal to the value of s. Each successive ‘step’ of the pyramid (made up of branch nodes) is equal to s-2 until the pyramid comes to a point (of 1 node, or two nodes). Odds produce pyramids that come to a point of 1 node, evens come to a point of 2 two nodes.
To check this I wanted to know what the point of the pyramid would be for C=100. The point of the pyramid is made up of nodes that represent triangles with two conditions 1) side lengths A = B and 2) A+B approaches C+1. If the value of C is 100, no one triangle satisfies both conditions. But triangles (51,51,100) and (50,51,100) both get close. If the value is 99, triangle (50,50,99) alone satisfies the conditions. In other words, the tip of the pyramid with the (even) 100-node base has two nodes, and the tip of (odd) 99-node base pyramid has one node.
If you take the total number of nodes (trunk node + limb nodes + branch node) produced by each trunk node you get a sequence:
1, 2, 4, 6, 9, 12, 16, 20. . .
To me, this sequence doesn’t have an apparent pattern to it.
But if you treat the odds and evens separately you get:
Odds: 1, 4, 9, 16…
Evens: 2, 6, 12, 20…
The odds are obviously squares (x)(x) and the evens are (x)(x + 1).
To count all the triangles you have to take the sum of x^2 and add that to the sum of (x^2 + x). Not from 1 to 100, but one to 50 because you divided 100 by half into evens and odds.
Therefore, to get the solution evaluate: sum(1->50) of 2(x^2) + x = 87125
There is probably an easier way… but this is how I figured it out.
Formatting issues…
Oh no, the formatting of my “rules in action” section totally didn’t work.
Here is another way of representing it:
Now the equilaterals are going down the page)
(1,1,1)
(2,2,2)
(1,2,2)
(3,3,3)
(2,3,3)(2,2,3)
(1,3,3)
(4,4,4)
(3,4,4) (3,3,4)
(2,4,4) (2,3,4)
(1,4,4)
(5,5,5)
(4,5,5) (4,4,5)
(3,5,5) (3,4,5) (3,3,5)
(2,5,5) (2,4,5)
(1,5,5)
|
|
| —(branch nodes)—>
(limb nodes) —(branch nodes)—>
|—(branch nodes)—>
|
|
V
Cool – thanks!