# A COVID-19 puzzle: How large a class do you need to fit 30 pupils?

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.

• Are students point objects? – Galen May 22 '20 at 16:10
• I have managed to solve it with a 0m x 0m room. Unfortunately, it is 58m high. – Joel Rondeau May 22 '20 at 20:24
• @JoelRondeau An interesting architectural challenge for future schools. – fomin May 23 '20 at 16:26
• 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. – Ben Jackson May 23 '20 at 17:00
• @BenJackson Please post a follow up question! – Anush May 23 '20 at 17:12

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): 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.

• I think you are missing the number after "The area is" – Anush May 22 '20 at 18:02
• @Anush that's an example of 'you can do the math' ... – Glorfindel May 22 '20 at 18:19

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

• This is a very nice way of doing it! – Anush May 22 '20 at 18:04
• 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 :) – Oray May 23 '20 at 16:28
• 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. – BlueRaja - Danny Pflughoeft May 23 '20 at 20:04
• @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. – RobPratt May 23 '20 at 20:26
• 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. – Clement Jan 9 at 9:03

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

• A rectangular grid is not optimal. – Anush May 23 '20 at 5:03 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.

• 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. – Rand al'Thor May 23 '20 at 13:44
• "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. – Num Lock May 25 '20 at 6:53