New from the MySociety genii:, capsule the curiously-capitalised PlaceOpedia. Think Google Maps ? Wikipedia. Brilliant. Except that, as I write, all the links read

## 11 Comments

### Leave a Reply

© 2017 The Daily Grind

Theme by Anders Norén — Up ↑

© 2017 The Daily Grind

Theme by Anders Norén — Up ↑

2 March, 2006 at 12:07 pm

This is a pretty tricky problem and I’ll miss my deadline if I don’t stop thinking about it. Here’s the story so far.

Suppose

Ppeople meet in groups ofG, with each person involved innmeetings andmmeetings overall. Then we certainly needn(G-1) = P-1(each person meets everyone else) andmG=nP(so the total number of person-meetings can be counted either way). (Sanity check,P=1,G=PandG=2can all satisfy these conditions.) I don’t know if these conditions are sufficient, but it’s worth mucking about with them.I fear for your hypothesis: if

G-1dividesP-1it’s not going to dividePunlessGis2orP.A BF&I search for a solution should be pretty easy to knock up in Haskell. Some sort of explanation may take longer…

2 March, 2006 at 4:30 pm

Drat. And there, I thought I’d done a sanity check on the (

P-1)/(G-1) thing.Thanks for the contribution. Hopefully you’ll either revisit it or somebody else will pick up the pieces. And I’m glad it’s not trivial, or I’d have felt really

reallystupid.2 March, 2006 at 8:13 pm

I just knocked up said BF&I search. With almost no account taken of symmetry, it eats those cycles. It gets 7, 9 and 15 in groups of 3 without any problem, and 13 in 4, 21 in 5, but after that the state space kind of explodes. Still, I only need one processor for LaTeX…

More anon. I smell prime number weirdness.

3 March, 2006 at 2:06 pm

Can people sit out a “round” or does everyone have to be in a group every round? (I seem to have forgotten a lot in the last 10 years…)

3 March, 2006 at 2:09 pm

No, let’s keep it simple – everyone’s involved in every round. I realise that this isn’t going to work for all

P.3 March, 2006 at 10:29 pm

That cuts things down because it requires

Gto dividePas well asG-1dividingP-1. It rules out a lot of solutions, eg the old Five Nations rugby. Thank goodness for the Italians.4 March, 2006 at 11:20 am

G=2 and P=2^n looks doable quite easily but probably too boring (I assume you really want G>2) (think speed dating rotation then split and repeat). 9 into 3 is doable on paper (the “it just works method”) but no inspriration here for any generalisation.

4 March, 2006 at 11:28 am

The first link you give in the update seems to suggest that P=p^2 with G=p is doable – he even offers a web page giving a solution – socials squares section!

4 March, 2006 at 11:36 am

In this situation, we need to see how the number of meetings scales with the group size: the whole session will collapse if the number of meetings is too great (ie. everyone in pairs), or the group size is too large (eg: the entire population).

4 March, 2006 at 12:08 pm

Ah. OK, I finally read that first link and at least

triedto squeeze it into my tiny brain. Looks like it’s only solvable for square number populations, though I don’t understand how that tallies with squares of primes.Of course, if I’d only read the link

beforeI got excited about a partial solution I thought I had, I’d have saved a lot of time. But hey, where’s the fun in that?4 March, 2006 at 2:17 pm

I’ll believe

G=p,P=p^2. Find a round room; putplong tables in it like spokes and label the seats at each table0..p-1from the centre out. At each change, you look at the labellon your seat and move to the seat labelledlwhich isltables clockwise from where you were. The0‘s (thesitters) stay put in the middle, the1–moversmove round in steps of1, thep-1-movers whizz round the rim so fast they look like they’re going backwards! When you’ve hadprounds of this, go find the others with the same label (in the same orbit) as yourself.This works for primes

pbecause thel-movers never see the same sitter twice:0,l,2l,…,(p-1)lall have different remainders (ie table numbers) on division byp. (Check: ifil = ap + bandjl = cp + b, then(i-j)l = (a-c)pwithp>land hence(i-j)>(a-c); so(i-j)andpmust have a common factor strictly between1andp; oops.) To see that thel-movers don’t see the samel’-mover twice either, spin the room at ratelso they appear to be the sitters and reapply the above.Dunno if these are the only solutions. My program makes a plan for 15 in groups of 3:

[“abc”, “ade”, “afg”, “ahi”, “ajk”, “alm”, “ano”, “bdf”, “beg”, “bhj”, “bik”, “bln”, “bmo”, “cdg”, “cef”, “chk”, “cij”, “clo”, “cmn”, “dhl”, “dim”, “djn”, “dko”, “ehm”, “eil”, “ejo”, “ekn”, “fhn”, “fio”, “fjl”, “fkm”, “gho”, “gin”, “gjm”, “gkl”]. But I haven’t checked that it splits into 7 rounds of 5 meetings yet.

Haskell’s a really good language for this sort of thing: doing all the accumulating and backtracking is practically effortless. But if you ain’t seen nuthin’ like it, then it’s a pretty wild ride…