Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I need help to answer the following question:
Is it possible to place 26 points inside a rectangle that is $20\, cm$ by $15\,cm$ so that the distance between every pair of points is greater than $5\, cm$?
I haven't learned any mathematical ways to find a solution; whether it maybe yes or no, to a problem like this so it would be very helpful if you could help me with this question.
No, it is not. If we assume that $P_1,P_2,\ldots,P_{26}$ are $26$ distinct points inside the given rectangle, such that $d(P_i,P_j)\geq 5\,cm$ for any $i\neq j$, we may consider $\Gamma_1,\Gamma_2,\ldots,\Gamma_{26}$ as the circles centered at $P_1,P_2,\ldots,P_{26}$ with radius $2.5\,cm$. We have that such circles are disjoint and fit inside a $25\,cm \times 20\,cm$ rectangle. That is impossible, since the total area of $\Gamma_1,\Gamma_2,\ldots,\Gamma_{26}$ exceeds $500\,cm^2$.
Highly non-trivial improvement: it is impossible to fit $25$ points inside a $20\,cm\times 15\,cm$ in such a way that distinct points are separated by a distance $\geq 5\,cm$.
Proof: the original rectangle can be covered by $24$ hexagons with diameter $(5-\varepsilon)\,cm$. Assuming is it possible to place $25$ points according to the given constraints, by the pigeonhole principle / Dirichlet's box principle at least two distinct points inside the rectangle lie in the same hexagon, so they have a distance $\leq (5-\varepsilon)\,cm$, contradiction.
Further improvement:
the depicted partitioning of a $15\,cm\times 20\,cm$ rectangle $R$ in $22$ parts with diameter $(5-\varepsilon)\,cm$ proves that we may fit at most $\color{red}{22}$ points in $R$ in such a way that they are $\geq 5\,cm$ from each other.
Jack D'Aurizio's answer is nice, but I think the following is probably the solution intended by whoever posed the puzzle:
Note that $26=5^2+1$. So perhaps we can divide our $20\times15$ rectangle into $5^2$ pieces, apply the pigeonhole principle, and be done. That would require that our pieces each have diameter at most 5. Well, what's the most obvious way to divide a $20\times15$ rectangle into $5^2$ pieces? Answer: chop it into $5\times5$ rectangles, each of size $4\times3$. And lo, the diagonal of each of those rectangles has length exactly 5 and we're done.
Although the conclusion is correct, the reasoning in this answer is not. The premise I started from does not apply to the question asked.
(After not finding any apparent community standard for what to do with this sort of incorrect answer, I decided to leave it in place - so that no-one else will duplicate it, and to preserve whatever value it may have, - but with the above note to prevent confusion.)
tl-dr; No.
This can be thought of as a circle packing question: treat each point as the center of a circle, and the distance no greater than constraint becomes a circles don't overlap constraint. (It's a little different from the usual "how many circles will fit", because this question is "how many circle-centers will fit" with the rest of each circle allowed to stick out of the rectangle.)
The densest packing of circles that don't overlap is the hexagonal tiling, where each circle is contained by (or inscribed in) a hexagon. (The description where center of each circle is also the center of a hexagon, and the centers of the nearest neighboring circles are the vertices of that hexagon, gives the same arrangement of circles but with larger hexagons; The following may be easier to understand with non-overlapping hexagons.)
The question can be restated as: At a 5cm spacing, will 26 hexagon centers fit inside a 20×15cm rectangle?
We can start by putting one in a corner; this might not be necessary, but it covers the minimum area within the rectangle so there's no better starting point.
Since the hex tiling has straight lines at minimum spacing, we can put a line of points along an edge of the rectangle - along the 20cm edge we can put 5 points (the last of which is on another corner).
Alongside that first line of hexagons we can put another line of hexagons, also spaced 5cm from eachother, which will be $\frac{5\cdot\sqrt{3}}{2} \approx 4.33$cm away from the first line. (Because that's the height of an equilateral triangle with 5cm sides, and the points in the second line are necessarily positioned to make equilaterial triangles with the points in the first line.)
With that line spacing, after the initial line, $\left \lfloor\frac{15\cdot2}{5\cdot\sqrt{3}}\right\rfloor=\left\lfloor\frac{15}{4.33}\right\rfloor=\left\lfloor3.36\right\rfloor=3$ more lines of hexagons will have some centers within the rectangle. Because of the positions of the centers along the lines, they will alternate having 5 and 4 centers within the rectangle.
So the total number of centers within the rectangle will be $5+4+5+4=18$. But that might not be a maximum; it might be possible to get more with a different orientation.
The obvious next orientation to try is with the first line along the 15cm side: $\left\lfloor\frac{20}{4.33}\right\rfloor=\left\lfloor4.62\right\rfloor=4$, so the total number of centers within the rectangle this way will be $4+3+4+3+4=18$.
Is there another orientation that could fit more? The diagonal of the rectangle is $\sqrt{20^2+15^2}=25$, just enough to fit 6 centers along the diagonal. The height of the 15-20-25 triangles on each side is 12cm, so there is room for 2 lines on either side of the diagonal. The first line on each side partitions off a similar triangle with $\frac{12-4.33}{12}\approx0.64$ of the height, so it has a base of $0.64\times25\approx15.98$, so at most 4 centers can be on each of those lines. The second line on each side partitions off a similar triangle with $\frac{12-2\cdot4.33}{12}\approx0.28$ of the (original) height, so it has a base of $0.28\times25\approx6.96$, so at most 2 centers can be on each of those lines. Without considering alignment this gives an upper bound, the maximum number of centers within the rectangle this way is $2+4+6+4+2=18$.
This is not a rigorous proof, but it's enough to convince me. With a minimum distance of exactly 5cm, only 18 points can fit into the rectangle, so with all distances strictly greater than 5cm it is not possible to place 26 points.
the densest packing of circles that don't overlap is the hexagonal tiling doesn't apply here. This is only true in the infinite plane, not necessarily so in a bounded polygon. See e.g. Circle packing in a square for examples of optimal packings which are not based on hexagonal tiling.
$\endgroup$
densest packing of circles argument. I suggest you read Jack D'Aurizio's answer more carefully.
$\endgroup$