27

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.

RobPratt
  • 13,685
  • 1
  • 29
  • 56
Simd
  • 7,845
  • 2
  • 34
  • 79
  • 1
    rot13(N gevnathyne tevq jbhyq nyybj sbe gur gvtugrfg cnpxvat, ubjrire vg jbhyqa'g arprffnevyl nyybj nal fghqrag gb zbir naq gurersber fbzr ebbzf pnaabg or bpphcvrq rira vs gur cnpxvat cerfreirf gur qrfverq fcnpvat.) – Galen May 22 '20 at 16:08
  • 12
    Are students point objects? – Galen May 22 '20 at 16:10
  • @Galen Yes they are. – Simd May 22 '20 at 16:35
  • @Galen They can move along the perimeters of the circles can't they if they need to leave the room, for example. – Simd May 22 '20 at 16:36
  • @Anush Yeah, it makes sense that they could traverse as close as the perimeters of the other students to leave the room. – Galen May 22 '20 at 17:09
  • 79
    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
  • 7
    @JoelRondeau An interesting architectural challenge for future schools. – Simd May 23 '20 at 16:26
  • 11
    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
  • 5
    @BenJackson Please post a follow up question! – Simd May 23 '20 at 17:12
  • I made kind of a follow-up here: https://puzzling.stackexchange.com/q/98500/69519 –  May 23 '20 at 21:21
  • 1
    @JoelRondeau - nice try - 1. 0x0 means they're extremely thin students. 2. they're not very tall, either - less than 1mm. 3. But 36 readers haven't noticed... – Tim May 24 '20 at 14:23
  • 2
    @Tim, OP clearly stated that students are point objects. Otherwise I would have modified my numbers accordingly. – Joel Rondeau May 24 '20 at 15:02
  • 1
    @JoelRondeau - o.k., I get the point! – Tim May 24 '20 at 16:05
  • If they apparently don't have teachers anyway why can't the point object students learn from home? – user3819867 May 25 '20 at 13:06
  • 2
    @user3819867 The dot nearest the door is reserved for a very skinny teacher. – Simd May 25 '20 at 14:14
  • @BenJackson: you mean the room design can't play human-Tower-of-Hanoi with the little ones? But that's 'classroom learning'... – smci Oct 16 '20 at 18:33

4 Answers4

25

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.

Ian MacDonald
  • 12,806
  • 1
  • 33
  • 63
Glorfindel
  • 28,033
  • 9
  • 96
  • 142
24

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

RobPratt
  • 13,685
  • 1
  • 29
  • 56
  • 1
    This is a very nice way of doing it! – Simd May 22 '20 at 18:04
  • 1
    Could you try to apply this optimization for another question asked before: https://puzzling.stackexchange.com/questions/54963/the-farmer-and-the-olive-trees/54966#54966 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
  • 4
    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 09 '21 at 09:03
  • @Clement I didn't find any better solution for that variant, but that is no guarantee that one doesn't exist. – RobPratt Jan 09 '21 at 22:26
  • Hi Rob, have you any idea of how global optimality could be proven? I run BARON over this model but without success. I thought if we could provide an expresion for lower bounds, that would help? I suppose we cannot even assume that the optimal result is rows of circles of the same diameter. – Clement Jan 10 '21 at 19:46
  • @Clement BARON is a global solver so should solve if you give it enough time. The only modifications needed to the above formulation are to change the first two constraints to $1 \le x_i \le w-1$ and $1 \le y_i \le h-1$. – RobPratt Jan 10 '21 at 20:05
1

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

Naresh Teli
  • 53
  • 3
0

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.

Dr. Motilal Panigrahi
  • 17
  • 1
  • 6
    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
  • 1
    "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 06:53