1
$\begingroup$

Using pigeonhole principle, it's possible to show that for any $n^2+1$ points in an equilateral triangle of side length $1$, there exists two points with distance at most $\frac{1}{n}$. How do I select $n^2$ points such that the distance between any two points have a distance of more than $\frac{1}{n}$?

$\endgroup$
3
$\begingroup$

Bit of a trick question. Got it wrong the first time. Then drew some pictures.

This is impossible for large $n,$ although easy enough for $n=2.$ For each point, draw a circle of radius $1/(2n)$ around it. No other circle can overlap this area, which is $\pi/(4 n^2).$ As we have $n^2$ points, we have a total area of at least $\pi / 4 \approx 0.785.$ The majority of this area is completely contained inside the triangle. This poses a problem, as the triangle of edge length $1$ has area $\sqrt 3 / 4 \approx 0.433$

A careful proof would take into account the amount of area that can be outside the big triangle. This is, essentially, the area of $3n$ semicircles, or roughly $3 \pi / (8 n) \approx 1.178/n.$ We should also add nearly three entire circles, for the three vertices.

The task is impossible once $$ \frac{\pi}{4} - \frac{3 \pi}{8n} - \frac{3 \pi}{4 n^2} > \frac{\sqrt 3}{4} $$

This can be made more accurate using the area of the regular hexagon that circumscribes each circle.

Added: this problem can be described as an ordinary circle packing problem if we take the (slightly larger) equilateral triangle with edges moved a distance of $1/(2n)$ outwards. The way it works out, a reasonable problem is to try to place $n^2$ points in a regular hexagon of exactly double the are of the triangle. this means the edges are $1/\sqrt 3.$ See diagrams

enter image description here

enter image description here

Alright, gave it a try. With $n=10,$ I can get more than $100$ points at pairwise distance exactly $1/10.$ However, in order to have a little remaining room so as to expand slightly and get the points more than $1/10$ apart, i can fit only $97$ points.

enter image description here

| cite | improve this answer | |
$\endgroup$

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.