HMMT 二月 2016 · 冲刺赛 · 第 22 题

英文解析

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 passesthrough 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 distancer 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 thenice 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 2
    value corresponds to a unique nice circle. By Fermat’s Christmas theorem, an integer is the sum oftwo squares if an only if in its prime factorization, each prime that is 3 mod 4 appears with an evenexponent (possibly 0.) In addition, since squares are 0, 1, or 4 mod 8, we can quickly eliminate integersthat 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 primefactor or write ”nice” with the prime factorization.
    626: nice (2 · 313)
    628: nice (2 · 157)2
    629: nice (17 · 37)
    632: 79
    633: 3
    634: nice (2 · 317)
    636: 3
    637: nice (7 · 13)2
    640: nice (2 · 5)7
    641: nice (641)
    642: 3
    644: 7
    645: 3
    3 4
    648: nice (2 · 3 )
    649: 11
    650: nice (2 · 5 · 13)2
    652: 163
    653: nice (653). There are 10 nice circles that intersect AB.