Putnam 1994

Problem A5

Given a sequence of positive real numbers which tends to zero, show that every non-empty interval (a, b) contains a non-empty subinterval (c, d) that does not contain any numbers equal to a sum of 1994 distinct elements of the sequence.



Let the sequence be rn. Let Sk be the set of all sums of k distinct elements of the sequence. We prove the result by induction on k.

Consider first k = 1, so we are given an interval (a, b). If b <= 0, there is nothing to prove. If b > 0, take a subinterval (c, b) with c > 0. Then for all n > some N, we have rn < c and hence rn ∉ (c, b). So there are only finitely many ri in (c, b). Hence we can pick an interval that lies between two of them.

Now assume the result for k, so given (a, b), take (c', d) which does not intersect Sk. Let h > 0 be half the width of (c', d), so that c = c'+h is the midpoint of (c', d). Then we can find m such that ri < h for i > m. Now take a sum s in Sk+1. If it falls in (c, d), then the last term must be one of r1, ... , rm, because if it was a later term, then it would be smaller than h and hence the sum of the first k terms in s would fall in (c', d) [contradicting the choice of (c', d).]. Now by induction on m we can find a subinterval of (c, d) which also excludes sums with last term r1, ... , or rm. Consider the interval (c-r1, d-r1). We can find a subinterval (e, f) of this which does not intersect Sk. Now (c1, d1), where c1 = e + r1, d1 = f + r1, is a subinterval of (c, d) and does not contain any sum s in Sk+1 with last term r1 (or any ri with i > m). In the same way we find a subinterval (c2, d2) of (c1, d1) which does not contain any sum s with last term r2 (or r1 or ri with i > m, since it is a subinterval). And so on.



Putnam 1994

© John Scholes
12 Dec 1998