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

$\endgroup$
  • 9
    $\begingroup$ Are students point objects? $\endgroup$ – Galen May 22 at 16:10
  • 66
    $\begingroup$ I have managed to solve it with a 0m x 0m room. Unfortunately, it is 58m high. $\endgroup$ – Joel Rondeau May 22 at 20:24
  • 6
    $\begingroup$ @JoelRondeau An interesting architectural challenge for future schools. $\endgroup$ – fomin May 23 at 16:26
  • 9
    $\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 May 23 at 17:00
  • 5
    $\begingroup$ @BenJackson Please post a follow up question! $\endgroup$ – Anush May 23 at 17:12
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$
  • 3
    $\begingroup$ I think you are missing the number after "The area is" $\endgroup$ – Anush May 22 at 18:02
  • 5
    $\begingroup$ @Anush that's an example of 'you can do the math' ... $\endgroup$ – Glorfindel May 22 at 18:19
25
$\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$
  • 1
    $\begingroup$ This is a very nice way of doing it! $\endgroup$ – Anush May 22 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 May 23 at 16:28
  • 3
    $\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 May 23 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 May 23 at 20:26
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$
  • 9
    $\begingroup$ A rectangular grid is not optimal. $\endgroup$ – Anush May 23 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$
  • 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 May 23 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 May 25 at 6:53

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.