Prove that for every positive integer m we can find a finite set S of points in the plane, such that given any point A of S, there are exactly m points in S at unit distance from A.
Solution
Take a1, a2, ... , am to be points a distance 1/2 from the origin O. Form the set of 2m points ±a1 ±a2 ± ... ±am. Given such a point, it is at unit distance from the m points with just one coefficient different. So we are home, provided that we can choose the ai to avoid any other pairs of points being at unit distance, and to avoid any degeneracy (where some of the 2m points coincide).
The distance between two points in the set is |c1a1 + c2a2 + ... + cmam|, where ci = 0, 2 or -2. So let us choose the ai inductively. Suppose we have already chosen up to m. The constraints on am+1 are that we do not have |c1a1 + c2a2 + ... + cmam + 2am+1| equal to 0 or 1 for any ci = 0, 2 or -2, apart from the trivial cases of all ci = 0. Each | | = 0 rules out a single point and each | | = 1 rules out a circle which intersects the circle radius 1/2 about the origin at 2 points and hence rules out two points. So the effect of the constraints is to rule out a finite number of points, whereas we have uncountably many to choose from.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
8 Oct 1998
Last updated/corrected 14 Mar 03