HMMT 二月 2018 · 冲刺赛 · 第 18 题
HMMT February 2018 — Guts Round — Problem 18
题目详情
- [ 10 ] Compute the number of integers n ∈ { 1 , 2 , . . . , 300 } such that n is the product of two distinct primes, and is also the length of the longest leg of some nondegenerate right triangle with integer side lengths.
解析
- [ 10 ] Compute the number of integers n ∈ { 1 , 2 , . . . , 300 } such that n is the product of two distinct primes, and is also the length of the longest leg of some nondegenerate right triangle with integer side lengths. Proposed by: Answer: 13 Let n = p · q for primes p < q . If n is the second largest side of a right triangle there exist integers c, a 2 2 2 such that a < pq and ( pq ) = c − a = ( c − a )( c + a ). Since c − a < c + a there are three cases for the values of c − a, c + a , and in each case we determine when a < pq . 2 2 p q − 1 2 2 (a) c − a = 1 and c + a = p q : Then a = > pq , so there are no solutions. 2 2 pq − p 2 (b) c − a = p and c + a = pq : Then a = > pq . 2 2 2 q − p 2 2 (c) c − a = p and c + a = q . Then a = which we require to be less than pq . This is equivalent 2 to 2 2 q − p < pq 2 2 2 q < 2 pq + p 2 2 2 q < ( q + p ) √ 2 q < q + p √ ( 2 − 1) q < p < q So the problem is equivalent to finding the number of distinct prime pairs ( p, q ) such that pq < 300 √ and ( 2 − 1) q < p < q . There are 13 such pairs: { (3 , 5) , (3 , 7) , (5 , 7) , (5 , 11) , (7 , 11) , (7 , 13) , (11 , 13) , (11 , 17) , (11 , 19) , (11 , 23) , (13 , 17) , (13 , 19) , (13 , 23) } and 13 · 23 = 299 which is the biggest such pair. √ 3 The most interesting borderline case are (3 , 7) : ≈ . 42 > 2 − 1, which leads to the (20 , 21 , 29) triangle, 7 √ √ 5 7 (5 , 13) : ≈ . 385 < 2 − 1, which leads to the (65 , 72 , 97) triangle, and (7 , 17) : ≈ . 411 < 2 − 1 13 17 which leads to the (119 , 120 , 169) right triangle.