HMMT 十一月 2021 · THM 赛 · 第 8 题
HMMT November 2021 — THM Round — Problem 8
题目详情
- Let n be the answer to this problem. Find the number of distinct (i.e. non-congruent), non-degenerate triangles with integer side lengths and perimeter n .
解析
- Let n be the answer to this problem. Given n > 0, find the number of distinct (i.e. non-congruent), non-degenerate triangles with integer side lengths and perimeter n . Proposed by: Sheldon Kieren Tan Answer: 48 Solution: We explicitly compute the number of triangles satisfying the problem conditions for any n . There are three kinds of triangles: isosceles and scalene. (Equilateral triangles are isosceles.) • Case 1: Isosceles. A triangle with side lengths a, a, b must satisfy 2 a > b and 2 a + b = n . So 2 a can be any even integer in the interval ( n/ 2 , n ). There are thus b ( n − 1) / 2 c − b n/ 4 c triangles here. • Case 2: Scalene. A triangle with side lengths a, b, c must satisfy a, b, c < n/ 2 and a + b + c = n . ( ) ( ) n − 1 b n/ 2 c There are triples satisfying the second condition, 3 of which violate condition 1 (since 2 2 at most one side is at least n/ 2, we can do casework on which side). We then remove the isosceles triangles and divide by 6 to account for ordering the sides. If there are no equilateral triangles (i.e. if 3 - n ), our answer here is (( ) ( ) ) 1 n − 1 b n/ 2 c − 3 − 3( b ( n − 1) / 2 c − b n/ 4 c ) . 6 2 2 Otherwise, the answer is (( ) ( ) ) 1 n − 1 b n/ 2 c − 3 − 3( b ( n − 1) / 2 c − b n/ 4 c − 1) − 1 . 6 2 2 1 2 2 The key observation is that almost all triangles are scalene, and there are are roughly ( n / 2 − 3 n / 8) = 6 2 n / 48 scalene triangles. Hence, n ≈ 48. Checking n = 48 yields (( ) ( ) ) 1 47 24 (23 − 12) + − 3 − 3 · (23 − 12 − 1) − 1 = 48 . 6 2 2 Hence, the answer is 48. 2 Remark 1. In fact, the number of distinct triangles with perimeter n and integer sides is [ n / 48] when 2 n is even and [( n + 3) / 48] when n is odd, where [ · ] is the nearest integer function. This follows by analyzing n modulo 12. Remark 2. The problem statement originally omitted the condition n > 0, so an answer of 0 was also counted as correct.