Let R be the reals. Let S ⊆ R have n ≥ 2 elements. Let AS = { x ∈ R : x = (s + t)/2 for some s, t ∈ S with s ≠ t}. What is the smallest possible |AS|?
Solution
Answer: 2n - 3.
Easy.
{1, 2, ... , n} gives 2n - 3 averages, namely 1 1/2, 2, 2 1/2, ... , n - 1/2, so it remains to show that we cannot do better.
Suppose a1 < a2 < ... < an+1. Let S be the set {a1, a2, ... , an} and S' the set S ∪ {an+1}. Then x = (an + an+1)/2 > an, so x ∉ AS. Similarly, y = (an+1 + an-1)/2 > (an + an-1)/2, which is the largest element of AS, so y ∉ AS. Hence |AS'| ≥ |AS| + 2.
© John Scholes
jscholes@kalva.demon.co.uk
24 Dec 1998