HMMT 二月 2016 · 冲刺赛 · 第 22 题
HMMT February 2016 — Guts Round — Problem 22
题目详情
- [ 12 ] On the Cartesian plane R , a circle is said to be nice if its center is at the origin (0 , 0) and it passes through at least one lattice point (i.e. a point with integer coordinates). Define the points A = (20 , 15) and B = (20 , 16). How many nice circles intersect the open segment AB ? For reference, the numbers 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691 are the only prime numbers between 600 and 700.
解析
- [ 12 ] On the Cartesian plane R , a circle is said to be nice if its center is at the origin (0 , 0) and it passes through at least one lattice point (i.e. a point with integer coordinates). Define the points A = (20 , 15) and B = (20 , 16). How many nice circles intersect the open segment AB ? For reference, the numbers 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691 are the only prime numbers between 600 and 700. Proposed by: Answer: 10 The square of the radius of a nice circle is the sum of the square of two integers. The nice circle of radius r intersects (the open segment) AB if and only if a point on AB is a distance r from the origin. AB consists of the points (20 , t ) where t ranges over (15 , 16) . The distance from the √ √ √ √ √ 2 2 2 2 origin is 20 + t = 400 + t . As t ranges over (15 , 16) , 400 + t ranges over ( 625 , 656) , so the 2 nice circle of radius r intersects AB if and only if 625 < r < 656 . 2 The possible values of r are those in this range that are the sum of two perfect squares, and each such value corresponds to a unique nice circle. By Fermat’s Christmas theorem, an integer is the sum of two squares if an only if in its prime factorization, each prime that is 3 mod 4 appears with an even exponent (possibly 0.) In addition, since squares are 0, 1, or 4 mod 8, we can quickly eliminate integers that are 3, 6, or 7 mod 8. Now I will list all the integers that aren’t 3, 6, or 7 mod 8 in the range and either supply the bad prime factor or write ”nice” with the prime factorization. 626: nice (2 · 313) 2 628: nice (2 · 157) 629: nice (17 · 37) 632: 79 633: 3 634: nice (2 · 317) 636: 3 2 637: nice (7 · 13) 7 640: nice (2 · 5) 641: nice (641) 642: 3 644: 7 645: 3 3 4 648: nice (2 · 3 ) 649: 11 2 650: nice (2 · 5 · 13) 652: 163 653: nice (653). There are 10 nice circles that intersect AB.