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 need help to answer the following question:

Is it possible to place 26 points inside a rectangle that is 20cm by
15cm so that the distance between every pair of points is greater
than 5cm?

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.

Answer

No, it is not. If we assume that P1,P2,,P26 are 26 distinct points inside the given rectangle, such that d(Pi,Pj)5cm for any ij, we may consider Γ1,Γ2,,Γ26 as the circles centered at P1,P2,,P26 with radius 2.5cm. We have that such circles are disjoint and fit inside a 25cm×20cm rectangle. That is impossible, since the total area of Γ1,Γ2,,Γ26 exceeds 500cm2.

enter image description here

Highly non-trivial improvement: it is impossible to fit 25 points inside a 20cm×15cm in such a way that distinct points are separated by a distance 5cm.

enter image description here

Proof: the original rectangle can be covered by 24 hexagons with diameter (5ε)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 (5ε)cm, contradiction.

Further improvement:
enter image description here

the depicted partitioning of a 15cm×20cm rectangle R in 22 parts with diameter (5ε)cm proves that we may fit at most 22 points in R in such a way that they are 5cm from each other.

Attribution
Source : Link , Question Author : Aryan Patel , Answer Author : leo

Leave a Comment