52
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Do you know the pigeonhole principle? en.wikipedia.org/wiki/Pigeonhole_principle $\endgroup$ – md2perpe Jun 11 '17 at 21:59
  • $\begingroup$ @jwg, the question was asked to know if it's meaningful to refer to the pigeonhole principle. $\endgroup$ – md2perpe Jun 12 '17 at 15:06
  • $\begingroup$ Fair enough @md2perpe, sorry. $\endgroup$ – jwg Jun 12 '17 at 15:41
  • 2
    $\begingroup$ seems to me you can only fit 20, and that using the edge (ie, not "inside" the rectangle) and distance being greater or equal to 5, instead of only "greater than". The problem with the 2.5cm radius circle area being larger than rectangle area idea is that a dot on edge will have half its area inside rectangle, and a dot on corner only a quarter, so you cant just sum up area. $\endgroup$ – Tuncay Göncüoğlu Jun 13 '17 at 11:48
  • 1
    $\begingroup$ Let's eliminate the Car Talk Puzzler obfuscation and try to put 26 points in a 3cm by 4cm rectangle that are all at least 1 cm apart. $\endgroup$ – Spencer Jun 14 '17 at 2:17
104
$\begingroup$

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$.

enter image description here

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$.

enter image description here

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: enter image description here

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.

$\endgroup$
  • 3
    $\begingroup$ @Polyergic: without additional constraints: a rectangle is not the whole plane. The hexagonal lattice is clearly non-optimal in a $2\times 2$ square, for instance. You can fit $9$ points with mutual distances $\geq 1$ with a square lattice, way less with an hexagonal lattice. $\endgroup$ – Jack D'Aurizio Jun 12 '17 at 18:18
  • 2
    $\begingroup$ @Polyergic: the wild behaviour of the constrained problem is pretty clear from this Wikipedia page (en.wikipedia.org/wiki/Circle_packing_in_a_square) - sometimes the optimal packing is close to a square packing, sometimes it is closer to an hexagonal packing. $\endgroup$ – Jack D'Aurizio Jun 12 '17 at 18:22
  • 5
    $\begingroup$ I find the first part of the answer dubious. The total area of the circles doesn't matter because only their centers need to be inside the rectangle. Using that argument, you can't place 4 points inside a 5x5 square, because the area of 4 circles exceeds 25cm^2. But actually you can just place a point at each corner. $\endgroup$ – Andre Jun 13 '17 at 14:01
  • 2
    $\begingroup$ @Andre: this answer works as it is. If you like to use a different argument for proving something else, feel free to do it, but there isn't anything dubious in the first part. $26$ disjoint circles with total area $\geq 510\,cm^2$ cannot fit in a $500\,cm^2$ rectangle (that, again, is the area of an enlarged rectangle, not the original one), that is all I am saying. $\endgroup$ – Jack D'Aurizio Jun 13 '17 at 14:03
  • 3
    $\begingroup$ Yes, you are correct. I have overlooked that you are talking about an enlarged area, which is crucial to the argument. Thanks for the clarification. $\endgroup$ – Andre Jun 13 '17 at 14:10
97
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ pretty damn nifty! $\endgroup$ – Fattie Jun 12 '17 at 12:54
  • 24
    $\begingroup$ For those who did not immediately understand this: Since the diagonal of the small rectangles has length 5, any two points placed anywhere inside such a rectangle have distance at most 5. Now if we are placing 26 points then at least two of them have to be in the same rectangle (since there are only 25 of them) and hence violate the requirement of having greater than 5. $\endgroup$ – Carsten S Jun 12 '17 at 14:57
  • 1
    $\begingroup$ @Χpẘ I think the significance of 26 is that it is one more than 25 and you can partition the area into 25 sections in which if two points are in the same section then they must be within 5cm of each other. If the question asked for 25 points then you wouldn't be able to use this particular argument because you can easily place 25 points in 25 sections with just one point in a section. $\endgroup$ – Dason Jun 13 '17 at 12:43
  • 1
    $\begingroup$ Yes, I don't understand how following the "most obvious" way to slice up the space, and failing to achieve the outcome, demonstrates that there is no other way to achieve the outcome. Surely you need the optimal packing strategy? $\endgroup$ – Steve Bennett Jun 14 '17 at 1:25
  • 1
    $\begingroup$ Steve, I think you are misunderstanding (my fault, no doubt, for being too terse). By following the most obvious way to slice up the space, I prove that any way of choosing points must fail to keep them all 5 units apart -- because there are 25 boxes and 26 points, so two must be in the same box, and the boxes have diameter 5 units. The division into boxes is under our control; it's the choice of points that needs to be arbitrary, and so it is. $\endgroup$ – Gareth McCaughan Jun 14 '17 at 10:50
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is so much lower than the other answer that I fear I've missed something obvious. I'd appreciate it if anyone can point out what. $\endgroup$ – ShadSterling Jun 13 '17 at 21:33
  • 2
    $\begingroup$ For one thing 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$ – dxiv Jun 13 '17 at 21:43
  • 1
    $\begingroup$ That's immaterial, and the same objection holds in both cases. Besides, you started your answer by invoking the densest packing of circles argument. I suggest you read Jack D'Aurizio's answer more carefully. $\endgroup$ – dxiv Jun 13 '17 at 21:50
  • 1
    $\begingroup$ Notice that this problem is the same as 'how many circles will fit' in a rectangle that is enlarged by the circles's radius on each side (so, a $25\times 20$ rectangle). $\endgroup$ – Fimpellizieri Jun 14 '17 at 5:43
  • 1
    $\begingroup$ The densest packing of circles that don't overlap is the hexagonal tiling - this is still wrong. The claim is true in the plane, not in a generic $n\times m$ rectangle. Additionally, it is pretty trivial that we may put $20$ points at a distance $\geq 1$ from each other in a $3\times 4$ rectangle: it is enough to start from a vertex and follow a square grid. $\endgroup$ – Jack D'Aurizio Jun 18 '17 at 0:15

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.