Putnam 2000, Problem B-6

Let $B$ be a set of more than $2^{n+1}/n$ distinct points with coordinates of the form $(\pm 1, \pm 1, \ldots, \pm 1)$ in $n$-dimensional space with $n \geq 3$. Show that there are three distinct points in $B$ which are the vertices of an equilateral triangle.


Solution:
For each point \(P\) in \(B\), let \(S_P\) be the set of points with all coordinates equal to \(\pm 1\) which differ from \(P\) in exactly one coordinate. Since there are more than \(2^{n+1}/n\) points in \(B\), and each \(S_P\) has \(n\) elements, the cardinalities of the sets \(S_P\) add up to more than \(2^{n+1}\), which is to say, more than twice the total number of points. By the pigeonhole principle, there must be a point in three of the sets, say \(S_P, S_Q, S_R\). But then any two of \(P,Q,R\) differ in exactly two coordinates, so \(PQR\) is an equilateral triangle, as desired.