27
$\begingroup$

Some countries are proposing to reopen high schools soon. To ensure safety, they want to make sure that all pupils in a class are at least 2 m apart. To help them find the smallest room that can fit the pupils from one class, we need to solve the following puzzle.

Given 30 dots, what is the smallest area rectangle that can fit all the dots in with no two dots being less than 2 m apart?

For practical reasons, a classroom's width should be within 2 metres of its length.

Improve this question
$\endgroup$
16
  • 12
    $\begingroup$ Are students point objects? $\endgroup$
    – Galen
    Commented May 22, 2020 at 16:10
  • 80
    $\begingroup$ I have managed to solve it with a 0m x 0m room. Unfortunately, it is 58m high. $\endgroup$
    – Joel Rondeau
    Commented May 22, 2020 at 20:24
  • 7
    $\begingroup$ @JoelRondeau An interesting architectural challenge for future schools. $\endgroup$
    – Simd
    Commented May 23, 2020 at 16:26
  • 11
    $\begingroup$ To make this challenge much more difficult, add the requirement that any one student must be able to leave through a door (fixed but arbitrary location) without requiring anyone else to leave the room. $\endgroup$
    – Ben Jackson
    Commented May 23, 2020 at 17:00
  • 5
    $\begingroup$ @BenJackson Please post a follow up question! $\endgroup$
    – Simd
    Commented May 23, 2020 at 17:12

4 Answers 4

Reset to default
25
$\begingroup$

The solution that springs to (my) mind is to put them

in a triangular grid, either 6 rows of 5 (red + orange), or 5 rows of 6 (red + yellow):

enter image description here

6 rows of 5 have a width of $4\cdot2+1=9$ meter, and a height of $5\sqrt3 \approx 8.66$ meter. The area is $45\sqrt3 \approx 77.94$ m2.
5 rows of 6 have a width of $5\cdot2+1=11$ meter, and a height of $4\sqrt3 \approx 6.92$ meter. The area ($44\sqrt3$) is smaller but it doesn't meet the '2 meter difference between the dimensions' requirement.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ I think you are missing the number after "The area is" $\endgroup$
    – Simd
    Commented May 22, 2020 at 18:02
  • 6
    $\begingroup$ @Anush that's an example of 'you can do the math' ... $\endgroup$
    – Glorfindel
    Commented May 22, 2020 at 18:19
24
$\begingroup$

As in my answer to My Mother's Dish Collection, I used a nonlinear optimization solver, with variables $x_i$, $y_i$, $w$, $h$. The problem is to minimize $w\cdot h$ subject to: \begin{align} 0 \le x_i &\le w &&\text{for $i\in\{1,\dots,30\}$}\\ 0 \le y_i &\le h &&\text{for $i\in\{1,\dots,30\}$}\\ (x_i - x_j)^2 + (y_i - y_j)^2 &\ge 2^2 &&\text{for $1\le i<j\le 30$}\\ -2 \le w - h &\le 2 \end{align} The first two constraints make sure each point is contained in the rectangle, the third constraint enforces social distancing, and the fourth constraint enforces the difference of at most 2 between width and height.

The resulting $x$ and $y$ coordinates returned by the solver match @Glorfindel's hexagonal packing.

enter image description here

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ This is a very nice way of doing it! $\endgroup$
    – Simd
    Commented May 22, 2020 at 18:04
  • 1
    $\begingroup$ Could you try to apply this optimization for another question asked before: puzzling.stackexchange.com/questions/54963/… I want to make sure that my answer is right or not. and I will be appreciated if you share what solver you are using so I can look into it too :) $\endgroup$
    – Oray
    Commented May 23, 2020 at 16:28
  • 4
    $\begingroup$ I like this answer better because it shows the problem is equivalent to circle packing. If we wanted to solve for a 3-dimensional classroom, we'd just extend this logic to sphere packing. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented May 23, 2020 at 20:04
  • $\begingroup$ @Oray, I added an answer to the linked question. I used the SAS NLP solver, which does not guarantee a globally optimal solution for a nonconvex problem like this one, but I used the multistart option to increase the likelihood. $\endgroup$
    – RobPratt
    Commented May 23, 2020 at 20:26
  • $\begingroup$ Would it make any difference if we require that the circles lie within the rectangle? The current solution would then read: w = 11, h=10.66. This way we would obtain a lower bound of 30 * pi * sqr(D/2)= 94.2. $\endgroup$
    – Clement
    Commented Jan 9, 2021 at 9:03
1
$\begingroup$

Reactangular grid :

Class size is as X=number of student in row Y=number of student in column N= Total student A= Area

N < X*Y .......(1)

A=2(X-1)*2(Y-1) ....... (2)

-2 <=2(Y-1)LENGTH- 2 (X-1)WIDTH <=2

-1 <=Y-X <=1

SO

Y=X-1 OR X OR X+1 ...... (3)

We know that optimum solution exist is nearest square solution so using equation (1) and (3) the solution is x=6 AND y=5 or vice versa

So area is 80 sq. m

Improve this answer
$\endgroup$
1
  • 9
    $\begingroup$ A rectangular grid is not optimal. $\endgroup$
    – Simd
    Commented May 23, 2020 at 5:03
0
$\begingroup$

enter image description here

Since it is a class room we must take care that teacher also has some place and so taking this into account and also the fact that students will not be sitting on the wall. So the answer is 144sq m.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ This is a bit overly literal (the purely mathematical puzzle seems to be looking just for a way to place 30 points), and a rectangle formation isn't optimal anyway. $\endgroup$
    – Rand al'Thor
    Commented May 23, 2020 at 13:44
  • 1
    $\begingroup$ "help them find the smallest room" Even if we'd take the space for the teacher into account your answer isn't correct as every pupil has a distance of almost 2.83 m according to your diagram. That's far from being the smallest. $\endgroup$
    – Num Lock
    Commented May 25, 2020 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.