25th Putnam 1964

Problem A6

S is a finite set of collinear points. Let k be the maximum distance between any two points of S. Given a pair of points of S a distance d < k apart, we can find another pair of points of S also a distance d apart. Prove that if two pairs of points of S are distances a and b apart, then a/b is rational.




Since we are only interested in ratios, we may take k = 1 and the points to have coordinates x1 = 0, x2 ... , xn-1, xn = 1. Let these points generate a vector space V of dimension m over Q.

If m = 1, then every xi is a rational multiple of xn and hence rational, so the ratio of any two distances is rational.

Suppose that m > 1. Take a basis b1, b2, ... , bm for V as follows. Take b1 = 1. Let b2 = xt, for some irrational xt, then extend {b1, b2} to a basis. Then each xi is a unique rational linear combination of the bj. In particular, x1 = 0, xt = b2 and xn= b1. Now define a linear map f from V to Q as follows. Let f(b2) = r b2, where r is rational and sufficiently large that f(b2) > 1, and f(bi) = bi/2 for all other i.

Now suppose we take two distinct points in S, we can write them as ∑ ribi and ∑sibi, where all ri and si are rational. Hence their images under f are r r2b2 + ∑ ribi/2 and r s2b2 + ∑ sibi/2, where the summations exclude i = 2. These must be unequal, otherwise we would have a linear combination of bi with rational coefficients which was zero.

So there is a unique point x in S with f(x) maximum and a unique point y in S with f(y) minimum. Then f(x - y) is greater than f(d) where d is any other difference xi - xj. But every difference except xn - x1 and x1 - xn occurs at least twice, so x and y must be the endpoints. Now f(x1) = 0 and f(xn) = 1/2, so f(x - y) = 1/2. But f(xt - x1) = f(xt) = f(b2) > 1. Contradiction.



25th Putnam 1964

© John Scholes
5 Feb 2002