Consider a set of more than $\frac {2^{n+1}} {n}$ points $(n>2)$, chosen from the $2^n$ points of the $n$-dimensional space which have the coordinates $\{ \pm1, \pm1, ..., \pm1 \}$.

Show that there are $3$ points in the set that form an equilateral triangle. I don't know how to start, as I am new in combinatorics problems.

  • 1
    $\begingroup$ Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be put on hold. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ – Shahab Apr 25 '16 at 12:54

Using the pigeonhole principle (which the problem formulation clearly suggests to do), one can show that moreover there is an equilateral triangle with the side equal to $2\sqrt{2}$.

Consider the set $V$ of points of the form $\{\pm 1,\dots, \pm 1\}$ (these are vertices of an $n$-hypercube). Call two of them neighbors if they differ in exactly one coordinate (in other words, they are connected by an edge). Note that the distance between any two different points from $V$ with a common neighbor is $2\sqrt{2}$.

Now each of the chosen points has $n$ neighbors. So in total there are more than $2^{n+1}$ neighbors to the chosen points. Since there are $2^n$ points in $V$, by the pigeonhole principle, some element of $V$ is a neighbor to at least three of the chosen points. By the above remark, these three points form the desired equilateral triangle.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.