MHB Is an Equilateral Triangle Possible with Distinct Points in n-Dimensional Space?

[Ackbach]

Here is this week's POTW:

-----

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.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 270 - Jul 03, 2017

This was Problem B-6 in the 2000 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

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.