24th Putnam 1963

Problem B6

Let S = S0 be a set of points in space. Let Sn = { P : P belongs to the closed segment AB, for some A, B ∈ Sn-1}. Show that S2 = S3.



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

Now we claim that any point in the convex hull can be written as a sum ∑ λixi 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 = ∑1mλixi. But now we can find μi not all zero so that ∑1m μixi = 0 (3 equations, one for each coordinate) and ∑ μi = 0 (1 equation). But now P = ∑1mi + k μi)xi for all k and we still have ∑ (λi + k μi) = 1. Take the smallest λii 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 = λ1x1 + ... + λ4x4 for some non-negative λi with sum 1. If two or three of the λi are zero, then this shows that P is in S1. So suppose λ1, λ2, λ3 are all positive. Then P = (λ1 + λ2) (λ1x1/(λ1 + λ2) + λ2x2/(λ1 + λ2) ) + (λ3 + λ4) (λ3x3/(λ3 + λ4) + λ4x4/(λ3 + λ4) ), which shows that P is in S2.



24th Putnam 1963

© John Scholes
5 Feb 2002