30th BMO 1994 Problem 2 How many incongruent triangles have integer sides and perimeter 1994? Solution
: 82834. We assume a triangle is not allowed to be degenerate with zero area. Let t n be the number of incongruent triangles with perimeter n and integer sides. Calculating the first few terms, we find t 1 = t 2 = 0, t 3 = 1 (111), t 4 = 0, t 5 = 1 (122), t 6 = 1 (222), t 7 = 2 (133, 223), t 8 = 1 (233), t 9 = 3 (144, 234, 333). Suppose the triangle has sides a, b, c with a ≤ b ≤ c. The only restrictions are that a > 0 and a + b > c. Now consider a-1, b-1, c-1. This will be a triangle with perimeter 3 shorter unless a = 1 or a + b = c + 1. But if a = 1, then we must have b = c and hence a + b = c + 1. So a-1, b-1, c-1 is either a triangle or a degenerate triangle. Conversely, if a-1, b-1, c-1 is a triangle or a degenerate triangle, then a, b, c is a triangle. So if we put d n as the number of degenerate triangles with perimeter n (including those with shortest side zero), then t n+3 = t n + d n . Obviously d odd = 0. d 2n = the number of pairs a ≤ b with a + b = n, which is just [n/2] + 1 (for example 4 = 0 + 4 = 1 + 3 = 2 + 2). So we have t 1994 = t 1991 = t 1988 + 498 = t 1985 + 498 = t 1982 + 496 + 498 = t 1979 + 496 + 498 = t 1976 + 495 + 496 + 498 = ... = 1 + 3 + 4 + 6 + 7 + ... + 496 + 498. There are 498 x 2/3 terms, which can be grouped into pairs with sum 499 (1 and 498, 3 and 496 etc), so the sum is 166 x 499. Alternative solution Assume a ≤ b ≤ c. We must have c < 1994/2, so the largest possible value of c is 996. Also c ≥ 1994/3, so c ≥ 665. If c = 665, then the only solution is a = 664, b = 665. If c = 666, then the solutions are a = 662, b = 666, or a = 663, b = 665, or a = b = 664. Evidently if c is odd, then the number of pairs (a, b) is one greater than for c - 1 (if the smallest and largest possible a for c-1 are h and k, then the largest and smallest for c are h-2 and k-1), but if c is even then the number of pairs is two greater than for c-1 (the largest and smallest are h-2 and k). Hence the total number of possibilities is 1 + 3 + 4 + 6 + 7 + ... + 498 (for c = 996 the possibilities are a = 2 up to a = 499). 30th BMO 1994 © John Scholes jscholes@kalva.demon.co.uk 14 Aug 2002