### 24th Putnam 1963

**Problem B6**

Let S = S_{0} be a set of points in space. Let S_{n} = { P **:** P belongs to the closed segment AB, for some A, B ∈ S_{n-1}}. Show that S_{2} = S_{3}.

**Solution**

We have to show that S_{2} is already the convex hull of S. We can define the convex hull of points **x**_{i} i = 1, 2, ... , n as the collection of all points ∑ λ_{i}**x**_{i} with all λ_{i} non-negative and ∑ λ_{i} = 1. Given two such points P = ∑ λ_{i}**x**_{i} and Q = ∑ μ_{i}**x**_{i}, any point on the closed segment PQ can be written as λP + μQ with λ, μ non-negative and λ + μ = 1, but λP + μQ = ∑ (λ λ_{i} + μ μ_{i}) **x**_{i} and ∑ (λ λ_{i} + μ μ_{i}) = 1. So it follows immediately that all S_{n} are subsets of the convex hull.

Now we claim that any point in the convex hull can be written as a sum ∑ λ_{i}**x**_{i} with at most 4 non-zero terms. Suppose not. Then some point P requires at least m ≥ 5 terms. wlog we may take these to be the first m terms, so that P = ∑_{1}^{m}λ_{i}**x**_{i}. But now we can find μ_{i} not all zero so that ∑_{1}^{m} μ_{i}**x**_{i} = 0 (3 equations, one for each coordinate) and ∑ μ_{i} = 0 (1 equation). But now P = ∑_{1}^{m}(λ_{i} + k μ_{i})**x**_{i} for all k and we still have ∑ (λ_{i} + k μ_{i}) = 1. Take the smallest λ_{i}/μ_{i} and set k as its negative. Then λ_{i} + k μ_{i} = 0 but the other terms λ_{j} + k μ_{j} remain non-negative, so we have expressed P as a sum of less than m terms. Contradiction.

So given any P in the convex hull we may write (wlog) P = λ_{1}**x**_{1} + ... + λ_{4}**x**_{4} for some non-negative λ_{i} with sum 1. If two or three of the λ_{i} are zero, then this shows that P is in S_{1}. So suppose λ_{1}, λ_{2}, λ_{3} are all positive. Then P = (λ_{1} + λ_{2}) (λ_{1}**x**_{1}/(λ_{1} + λ_{2}) + λ_{2}**x**_{2}/(λ_{1} + λ_{2}) ) + (λ_{3} + λ_{4}) (λ_{3}**x**_{3}/(λ_{3} + λ_{4}) + λ_{4}**x**_{4}/(λ_{3} + λ_{4}) ), which shows that P is in S_{2}.

24th Putnam 1963

© John Scholes

jscholes@kalva.demon.co.uk

5 Feb 2002