Let X be the set of 2n points (±1, ±1, ... , ±1) in Euclidean n-space. Show that any subset of X with at least 2n+1/n points contains an equilateral triangle.
Solution
Let the subset be Y. For each point P in X let SP be the set of n points a distance 2 from P (in other words the points which differ from P in just one coordinate). The points in SP are all equidistant from each other (each pair is a distance 2√2 apart), so it is sufficient to show that at least one of the sets SP contains more than 2 points of the subset Y.
Each point of Y (indeed of X) is in just n sets SP, so ∑P |SP ∩ Y| = |Y| n > 2n+1. But there are 2n sets SP ∩ Y, so at least one of them must have more than 2 points.
© John Scholes
jscholes@kalva.demon.co.uk
1 Jan 2001