IMO 1967 LL CZS11

Origin: CZS

Problem

Let n be a positive integer. Find the maximal number of non- congruent triangles whose side lengths are integers less than or equal to n.

Solution

We have to find the number pn of triples of positive integers (a, b, c) satisfying a \leqb \leqc \leqn and a + b > c. Let us denote by pn(k) the number of such triples with c = k, k = 1, 2, . . ., n. For k even, pn(k) = k + (k −2) + (k −4) + \cdot \cdot \cdot + 2 = (k2 + 2k)/4, and for k odd, pn(k) = (k2 + 2k + 1)/4. Hence pn = pn(1)+pn(2)+\cdot \cdot \cdot+pn(n) = n(n + 2)(2n + 5)/24, for 2 | n, (n + 1)(n + 3)(2n + 1)/24, for 2 ∤n.