Given n reals αi ∈ [0, 1] show that we can find β ∈ [0, 1] such that ∑ 1/|β - αi| ≤ 8n ∑1n 1/(2i - 1).
Solution
The trick is to pick several candidates βj and then to take ∑j1/|βj - αi|.
Divide [0, 1] into 2n equal intervals, each width 1/2n. Then at least n of them do not contain any αi. Take the βj to be the midpoints of n empty subintervals. Then certainly |βj - αi| ≥ 1/4n. If we fix j, then we cannot say more than that, so we get ∑i 1/|βj - αi| ≤ n 4n, which is not good enough.
But if we fix i, then we can say more: at most two βj can be at the minimum distance 1/4n, at most two more at 3/4n, at most two more at 5/4n and so on. We now sum over j. We do not know whether there are one or two βj at each stage (because if αi is off-center, then fairly soon we run into the endpoint going one way, and so start getting just one βj). But it is certainly conservative to assume that we have two at each stage and go on for n pairs. So summing over j gives: ∑j 1/|βj - αi| < 8n ∑ 1/(2i - 1). Now summing over all ai multiplies the result by n. At least one bj must give a result that is not above average, so we can find β with the sum at most 8n ∑ 1/(2i - 1).
© John Scholes
jscholes@kalva.demon.co.uk
4 Dec 1999