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 distinctprimes, and is also the length of the longest leg of some nondegenerate right triangle with integer sidelengths.
解析
英文解析
- [ 10 ] Compute the number of integers n ∈ { 1 , 2 , . . . , 300 } such that n is the product of two distinctprimes, and is also the length of the longest leg of some nondegenerate right triangle with integer sidelengths.
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.
pq − p 22
(b) c − a = p and c + a = pq : Then a = > pq .2
2 22
q − p
2 2
(c) c − a = p and c + a = q . Then a = which we require to be less than pq . This is equivalentto 2
2 2
q − p < pq
2 22
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.
√
The most interesting borderline case are (3 , 7) : ≈ . 42 > 2 − 1, which leads to the (20 , 21 , 29) triangle,3
√ √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.