Welcome to our community

Be a part of something great, join today!

Problem of the Week # 270 - Jul 03, 2017

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
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 POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
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:

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.
 
Status
Not open for further replies.