x1 < x2 < x3 < ... is a sequence of positive reals such that lim xn/n = 0. Is it true that we can find arbitrarily large N such that all of (x1 + x2N-1), (x2 + x2N-2), (x3 + x2N-3), ... , (xN-1 + xN+1) are less than 2 xN?
Given 0 < k < x1, take N to be the largest n which maximises (xn - nk). k is chosen so that (x1 - k) is positive. Since xn/n tends to zero, only finitely many (xn - nk) are positive, so N is well defined. Now xN-m - (N - m)k ≤ xN - Nk and xN+m - (N + m)k < xN - Nk. Adding gives xN-m + xN+m < 2xN. So we are home provided we can show that this process generates arbitrarily large N.
The trick is to take k small. In particular, take k < (xN+1 - xN)/(N+1). Then xN+1 - (N+1)k > xN. A fortiori it is greater than all of xi - ki for i ≤ N. So the value corresponding to this k is bigger than N, which completes the proof.
62nd Putnam 2001
© John Scholes
16 Dec 2001