Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to Bhoddhisatva,scotia,Anonymous,Cornytiv34,Anonymous, for Donating to support the site

Social distancing 2

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Social distancing 2

#322926

Postby Gengulphus » July 1st, 2020, 10:59 am

Last Thursday, I happened to be awake and listening to Radio 4 when their daily puzzle was broadcast. That's not something I normally make a point of doing, partly because it's broadcast quite early (about 6:45 am) and partly because all too often it is extremely trivial. But this one was rather more difficult than most and on similar lines to the question discussed in the earlier "Social distancing" thread:

"A theatre has a perfectly square seating area. With a minimum 2 metre separation, it can fit at most 9 people, with no room to spare. How many can fit at most if the minimum separation is reduced to 1 metre?

(Note: Ignore the space each audience member takes up, and assume nobody needs to use the facilities in the middle.)
"

Their solution is obtainable by clicking on "> Click here for the answer" in the above link to the puzzle, though people might want to try it before looking there. That answer is correct as far as it goes, but for extra credit ;-), what is incomplete about it? And can you fill the gaps in it, preferably in a way that has a 'puzzle solution' flavour to it rather than a 'mathematical research problem' flavour?

I should perhaps say that I don't have an answer of the preferable type to that last question!

Gengulphus

UncleEbenezer
The full Lemon
Posts: 10658
Joined: November 4th, 2016, 8:17 pm
Has thanked: 1451 times
Been thanked: 2956 times

Re: Social distancing 2

#322937

Postby UncleEbenezer » July 1st, 2020, 11:38 am

(Note: Ignore the space each audience member takes up, and assume nobody needs to use the facilities in the middle.)"

Nice to see they've met a pedant ;)

The 'obvious' answer: it's a 4x4m area, on which the seating is a 3x3 point grid at 2m. The idea of facilities in the middle creates cognitive dissonance, so let's assume the pedant was heard but never got a chance to proof-read what was posted. At 1m, the 4x4m area becomes a 5x5 grid seating 25 points.

but for extra credit ;-), what is incomplete about it?


Lots of pedantic points of course. Is this about ways other than a square grid to pack a perfectly square area? Or something more related to a real-life auditorium, where packing is far from square?


I should add that back in the Bad Old Days, it would take just a single smoker to turn that entire auditorium foul (I couldn't go back to any cinema for 25 years after a traumatic experience aged 19). Which just goes to show how something nasty in the air can spread!

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Social distancing 2

#322959

Postby Gengulphus » July 1st, 2020, 12:43 pm

UncleEbenezer wrote:
(Note: Ignore the space each audience member takes up, and assume nobody needs to use the facilities in the middle.)"

Nice to see they've met a pedant ;)
...
... The idea of facilities in the middle creates cognitive dissonance, so let's assume the pedant was heard but never got a chance to proof-read what was posted. ...

Yes, indeed - it would more sensibly have been worded as "nobody in the middle needs to use the facilities". Or even as "nobody needs to use the facilities", given that quite a lot of carefully placed doors would be needed even to allow all of those at the edge of the auditorium to use the facilities!

UncleEbenezer wrote:... Or [is this about] something more related to a real-life auditorium, ...?

No, it's not about things related to a real-life auditorium - their note makes it pretty clear that real-life constraints don't apply and we're talking about a simple mathematical abstraction.

Otherwise, your solution in the stuff I haven't quoted is the same as theirs (though expressed more succinctly!), and indicates that you're thinking along the same lines as me about what the gaps in their solution are. But what precisely are those gaps, and can you fill them?

Gengulphus

malkymoo
Lemon Slice
Posts: 349
Joined: November 23rd, 2016, 9:45 am
Has thanked: 29 times
Been thanked: 116 times

Re: Social distancing 2

#322961

Postby malkymoo » July 1st, 2020, 12:58 pm

Gengulphus wrote:Otherwise, your solution in the stuff I haven't quoted is the same as theirs (though expressed more succinctly!), and indicates that you're thinking along the same lines as me about what the gaps in their solution are. But what precisely are those gaps, and can you fill them?

Gengulphus


It is not explicitly stated that all the seating is on a flat plane, is that the sort of thing you had in mind?

UncleEbenezer
The full Lemon
Posts: 10658
Joined: November 4th, 2016, 8:17 pm
Has thanked: 1451 times
Been thanked: 2956 times

Re: Social distancing 2

#322966

Postby UncleEbenezer » July 1st, 2020, 1:08 pm

Gengulphus wrote:Otherwise, your solution in the stuff I haven't quoted is the same as theirs (though expressed more succinctly!), and indicates that you're thinking along the same lines as me about what the gaps in their solution are. But what precisely are those gaps, and can you fill them?

Gengulphus


The gap I think you're getting at is in two parts:

(1) 4x4m is a minimum size. But the 9 maximum also applies to 4+ε, for values of ε up to a full two metres if we restrict ourselves to rigid square packing. For example, a 5x5m space would also take a 9-point square grid at 2m separation, but would take 6x6 at 1m.
(2) A square packing isn't necessarily the most efficient way to fill an area.

So the supplementary question now takes three parts:
(1) What is the minimum ε0 for which we could pack more than 9 at 2m separation, without the square grid assumption?
(2) How many could we then pack in at 1m?
(3) Is our ε0 also a threshold value for 1m packing, and what's the solution immediately below it?


I'm not working it out. Unless I get carried away after a glass or two of something I wouldn't touch at this hour.

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Social distancing 2

#323000

Postby Gengulphus » July 1st, 2020, 2:48 pm

UncleEbenezer wrote:
Gengulphus wrote:Otherwise, your solution in the stuff I haven't quoted is the same as theirs (though expressed more succinctly!), and indicates that you're thinking along the same lines as me about what the gaps in their solution are. But what precisely are those gaps, and can you fill them?

The gap I think you're getting at is in two parts:

(1) 4x4m is a minimum size. But the 9 maximum also applies to 4+ε, for values of ε up to a full two metres if we restrict ourselves to rigid square packing. For example, a 5x5m space would also take a 9-point square grid at 2m separation, but would take 6x6 at 1m.

You're ignoring the phrase "with no room to spare" in the problem: a (4+ε)x(4+ε)m square has room to spare around an enclosed 3x3 square grid of people at 2m spacings. Even if ε is too small to allow a 10th person to be accommodated, there is room to spare for people at two or more edges of the 3x3 packing to move around.

I can incidentally show that there are such values of ε - in particular, any value of ε less than 3sqrt(2) - 4 = 0.2426406871... definitely won't allow a 10th person to be accommodated, even with a completely free choice of packing. The proof is simple: divide the (4+ε)x(4+ε) square up into 3 equal parts along each dimension. This breaks it up into nine smaller squares, each of side < sqrt(2). Any two people within one of those smaller squares must be at distance < 2 from each other, so each of those nine smaller squares can only contain one person no matter what 2m-separation packing one chooses, and so any such packing can contain at most nine people.

FWIW, by the way, I spent a few hours last week similarly ignoring the phrase "with no room to spare" before I realised that it is there and is a constraint on the size of the square. I.e. I was trying to work out what the answer is if you're allowed spare room, just as long as it's not enough spare room to allow 10 people to fit (using any packing, without a restriction to square grids). I didn't succeed on my own, and even googling and 'Wikipedia'ing for relevant work by other people has only told me that the answer is very probably 33 - "very probably" because the best known packing of 34 people in a square would need to be improved quite a lot to make it 34.


UncleEbenezer wrote:(2) A square packing isn't necessarily the most efficient way to fill an area.

Yes, the gaps I've noticed are based on that - but what exactly are they? (Just identifying the gaps is a sufficient answer to that question - actually filling them seems harder, and quite possibly "a glass of two of something" is needed to tackle them... Though it also seems likely to make it yet harder! ;-)

Gengulphus

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Social distancing 2

#323005

Postby Gengulphus » July 1st, 2020, 3:04 pm

malkymoo wrote:
Gengulphus wrote:Otherwise, your solution in the stuff I haven't quoted is the same as theirs (though expressed more succinctly!), and indicates that you're thinking along the same lines as me about what the gaps in their solution are. But what precisely are those gaps, and can you fill them?

It is not explicitly stated that all the seating is on a flat plane, is that the sort of thing you had in mind?

No - it's about the mathematical abstraction as points in a square in a flat plane. I'm not being pedantic about ways in which the wording of the problem might be interpreted differently from what they pretty obviously intend. It's more about things their solution treats as obvious, but which actually require some justifying to make the solution complete.

Gengulphus

jfgw
Lemon Quarter
Posts: 2533
Joined: November 4th, 2016, 3:36 pm
Has thanked: 1096 times
Been thanked: 1145 times

Re: Social distancing 2

#323040

Postby jfgw » July 1st, 2020, 5:48 pm

I don't know about you but, when I have been to a theatre, I have had at least one other person with me. Given that we are ignoring people's dimensions, groups from the same household or bubble would take up no more space than one Billy-no-mates.

I suggest that the puzzle should specify that no two attendees are from the same household or bubble.


Julian F. G. W.

jfgw
Lemon Quarter
Posts: 2533
Joined: November 4th, 2016, 3:36 pm
Has thanked: 1096 times
Been thanked: 1145 times

Re: Social distancing 2

#323057

Postby jfgw » July 1st, 2020, 6:53 pm

There are a few different ways of trying to pack people into a 4m square:

Five on the bottom row, four on the next (between the gaps), then five, then four, then five would give 23 people with not enough room for any more.

Five staggered rows of four would give 20 people.

4, 3, 4, 3, 4, 3 doesn't allow room for another row and is only 21.

Staggered rows of 3 still only allow room for 7 rows so 21 people.

Now explore irregular packings.

It is also necessary to establish that nine people will not fit into a square smaller than 4m at 2m social distancing.

Julian F. G. W.

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Social distancing 2

#323209

Postby Gengulphus » July 2nd, 2020, 10:24 am

jfgw wrote:There are a few different ways of trying to pack people into a 4m square:

Five on the bottom row, four on the next (between the gaps), then five, then four, then five would give 23 people with not enough room for any more.

Five staggered rows of four would give 20 people.

4, 3, 4, 3, 4, 3 doesn't allow room for another row and is only 21.

Staggered rows of 3 still only allow room for 7 rows so 21 people.

Now explore irregular packings.

And also regular packings whose rows are not aligned to the sides of the square... For example, one might try placing a row of 6 along the diagonal of a 3-4-5 Pythagorean triangle nestled into a corner of the square, e.g. at positions (0,0), (0.8,0.6), (1.6,1.2), (2.4,1.8), (3.2,2.4) and (4,3), and then adding shorter parallel rows at distances sqrt(3)/2 to the sides of that row, but that turns out to only fit 19 people in.

But yes, showing that you cannot fit 26 people into a 4m square with 1m social distancing is one of the gaps I spotted - and because of the enormous number of conceivable irregular packings and orientations of regular packings, it's a hard gap to fill. Indeed, the only proof I've found in the research literature is one that a square of side about 4.1887491019565m is the smallest one that allows a 1m-separated packing of 26 people. It's a computer-aided proof with so many cases that the paper didn't list them, but instead gave a URL for a file containing them, so it's thoroughly unsuitable as a solution to a 'puzzle' as opposed to a 'mathematical research problem'! But of course, it is somewhat overkill for what this puzzle requires - it involves proving that all squares of sides even microscopically less than about 4.1887491019565m are not big enough to accommodate 26 people, whereas this puzzle only requires one to show that a 4m square isn't big enough. So there's an open question in my mind about how easily one can prove that a 4m square cannot accommodate 26 people at 1m social distancing, and in particular whether one can produce a simple enough proof for it to be a reasonable part of a 'puzzle' solution. So filling this gap currently seems to me more of a challenging problem than a puzzle - but perhaps someone can come up with a sufficiently simple proof?

jfgw wrote:It is also necessary to establish that nine people will not fit into a square smaller than 4m at 2m social distancing.

Yes, that's the other gap I spotted - it seems pretty obvious, but it's not entirely trivial to prove it. On this one, I do know of a reasonably comprehensible proof, but I'll leave it open for the time being to see what people come up with...

Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 4 guests