1
$\begingroup$

I've been given the following two problems, and I would like to know whether my approach is okay.

  1. Prove you can't arrange $100$ points in a $13\times 18$ rectangle such that the distance between every two points is at least $2$.
  2. Prove that if you arrange $4^n+1$ points in an equilateral triangle with side length $1$, at least two points will be distanced $\leq \frac 1{2^n}$.

My approach was just to use circles.

First thicken the rectangle appropriately by adding small pizza slices at the corners and extend side length, and then compare areas. If the area of the circles is too large, we're done.

For the second problem, the $4^n+1$ hints at subdividing an equilateral into four smaller ones, giving a much quicker answer. Still though, I don't see such an approach using the pigeonhole principle for the first one, and I'm not sure whether my approaches are fine.

Thanks!

$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

About $(1)$: assume that you may take $100$ points in a $13\times 18$ rectangle with the wanted property.
If we consider a unit circle centered at each point, these circles do not overlap. enter image description here

If we consider a centered $11\times 16$ sub-rectangle, the number of points lying in this rectangle, multiplied by $\pi$, cannot exceed the area of the original $13\times 18$ rectangle. It follows that at most $74$ points may lie in the inner rectangle. By a similar argument, assuming it is possible to take $100$ points $\geq 2$ apart from each other in a $13\times 18$ rectangle, $100\pi$ has to be smaller than the area of a $15\times 20$ rectangle. However, that is not the case.

About $(2)$, just use a sub-division like the following one: enter image description here

and the pigeonhole principle.

$\endgroup$
4
  • $\begingroup$ The same "thickening" argument works for the triangle as well, no? I.e elongate the sides by $\frac{1}{2^{n+1}}$ and show not enough circles of diameter $\frac{1}{2^{n+1}}$ fit inside... $\endgroup$
    – combinarcotics
    Sep 13, 2016 at 18:31
  • $\begingroup$ @combinarcotics: that may work, too, but I think it is easier to argue that if two points are constrained in a set with diameter $\frac{1}{2^n}$, the claim is straightforward to prove by the pigeonhole principle. $\endgroup$
    – Jack D'Aurizio
    Sep 13, 2016 at 18:37
  • $\begingroup$ Absolutely, I'm just making sure - the circle approach works for any shape? $\endgroup$
    – combinarcotics
    Sep 13, 2016 at 18:39
  • $\begingroup$ @combinarcotics: it works if the bound is loose enough. A tight bound requires the knowledge of the structure of the optimal circle-packing, that is a very difficult problem for arbitrary shapes. $\endgroup$
    – Jack D'Aurizio
    Sep 13, 2016 at 18:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .