43rd Putnam 1982

Problem A6

ai are real numbers and ∑1 ai = 1. Also |a1| > |a2| > |a3| > ... . f(i) is a bijection of the positive integers onto itself, and |f(i) - i| |ai| → 0 as i → ∞. Prove or disprove that ∑1 af(i) = 1.



Answer: it is false.

Take ai to be a sequence of terms with alternating signs, so that the sum of the odd terms diverges and the sum of the even terms diverges. To be specific, let us take the odd terms positive and the even terms negative. Now take the sequence f(1), f(2), f(3), ... to have runs of odd numbers followed by the corresponding even numbers. So it might start with 1, 3, 5, 7. The corresponding even numbers would then follow: 1, 3, 5, 7, 2, 4, 6, 8. At this point f(1), f(2), ... , f(8) is just a rearrangement of 1, 2, ... , 8. We then have another run of odd numbers, maybe 9, 11, 13, 15, 17, 19. Then the corresponding evens, 10, 12, ... , 20, so that f(1), f(2), ... , f(20) is just a rearrangement of 1, 2, ... , 20. No matter how long the runs, we will always have |f(n) - n| <= n for all n. So we can satisfy |f(n) - n| |an| → 0, provided that n an → 0.

Now since the sum of the odd terms diverges, we can take each run of odds long enough that its sum is at least 2. The sum up to the start of the run is just ∑1N ai for some large N and so is close to 1. In particular, for the mth run of odds, the sum up to the start of the run will certainly be at least 1/2 for all sufficiently large m. Hence the sum up to the end of the run is more than 2. So we get arbitrarily large partial sums which differ from ∑ ai by at least 1. So we cannot have ∑ af(i) = ∑ ai. In fact ∑ af(i) does not even converge, since we also have arbitrarily large partial sums (up to the start of each run of odds) which converge to 1.

It remains to exhibit an which satisfy |an| → 0. A suitable example is an-1 = (-1)n 1/(n ln n).



43rd Putnam 1982

© John Scholes
16 Jan 2001