Pigeonhole principle in geometric task

Question

Task: There was a camp opened outside the city. It is a forest area in the form of a circle, its radius is 250 meters, and there are some tables for tourists.

Tables stand on one leg and may be at a distance of not less than 10 meters one from another. Prove that this forest area can have NO more than 2601 table.

Tried to prove by dividing (area of forest circle) / (are of hexagon, which inradius is 5 meters), and so on, but always get less than 2601 tables (2373 or less). Have no idea, how to prove it. Sorry for bad English =)

Answer 1

It seems the number $2601$ was likely derived under the following assumptions:

• The leg of a table stands on a single point.
• You can put the leg of a table anywhere inside the given circle of radius $250,$ even on the circumference of the circle.
• The distance between any two table legs must be at least $10.$

We then observe that the "distance $10$" condition is enforced if we assume each table leg is at the center of a disk of radius $5$ that cannot overlap the disk around any other table leg. But we still allow the table leg to be placed at the edge of the forest, which means that part of the disk may be outside the circle of radius $250.$ In fact, the farthest point on the disk may be up to $255$ meters, but no further, from the center of the forest.

The conclusion is that the number of tables in the forest can be no greater than the number of disks of radius $5$ that can fit without overlap inside a circle of radius $255.$

We then observe that if there are $n$ disks, their total area is $25\pi n,$ which must be no greater than the area of the circle of radius $255$ in which the tables are to be placed. That is, $$ 25\pi n \leq \pi(255^2). $$ Solving this for $n,$ we find that $n \leq 2601.$

As you noticed, the actual upper bound is less than $2601,$ because (among other things) we cannot actually cover the entire area of a circle with non-overlapping smaller disks. But when you prove the number of tables has an upper bound that is less than $2601,$ you prove that $2601$ is an upper bound. For example, if the maximum number of tables in a forest were $2373,$ then it is certainly true that the number cannot be greater than $2601.$

To find the least upper bound would be very difficult, I think. But the problem does not ask you to find a least upper bound, only to show the validity of the upper bound named in the problem.

Answer 2

The total area of the forest area is $62500 \pi$. If we imagine each table as being a circle with the leg as the center, having a radius of $5$ meters, this guarantees that no two tables will be closer than $10$ meters apart as measured from leg-to-leg. Then the total area of $2601$ such tables is $$2601 \cdot 25 \pi = 65025 \pi > 62500 \pi.$$ Thus it is impossible to fit all of these tables into the forest area, since their total area exceeds the area they are allotted.

However, we can be even more tight with the bound, noting that the maximum circle packing density of equal sized circles in the plane was proved by Lagrange as $$\frac{\pi}{2\sqrt{3}}.$$ This means that if there are $n$ tables to be placed, the total area they would occupy would be bounded below by $$25n \pi \cdot \frac{2\sqrt{3}}{\pi} = 50n \sqrt{3},$$ and this gives us a sharper bound on the minimum number of tables that cannot fit: $n \ge 2268$.

If we allow the legs of the tables to be placed at the border of the forest area, then the above calculations can be adjusted by simply expanding the radius of the forest area by $5$ meters; this gives us exactly $65025 \pi$. But as mentioned before, the packing density of tables is not $1$, therefore it is impossible to fit $2601$ such tables. And revising the lower bound in the above calculation, we would have $n \ge 2359$.

Answer 3

The forest is a circle with radius $250$,so its total area is $\pi\times250^2$.
As the tables must stand a distance of $10$ from each other, we can assume each table has area $\pi\times 5^2$.
Dividing those two numbers, we get a maximum of $2500$ tables in the forest. However, some tables will be at the border of the forest, so they take less than $\pi \times 5^2$ space in the forest.

The optimal way, which might not be achieved, on the border will be a table at every $10$ meters of the border, so this will result in $2 \pi \times 250 / 10 = 50 \pi$ tables on the border. Those tables will only take a little more than $39$ m$^2$ from the area in the forest.
Thus we have $50 \pi \times ( \pi \times 25 - 39)$ m$^2$ area left, which allows for another $80$ tables.

So I can get no more than $2580$ tables, but by getting a worse estimate than $39$ m$^2$ inside the forest for border tables, $2601$ seems a reasonable number of maximum amount of tables.