More on Flickr »
New from the MySociety genii:, capsule the curiously-capitalised PlaceOpedia. Think Google Maps ? Wikipedia. Brilliant. Except that, as I write, all the links read
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 P people meet in groups of G, with each person involved in n meetings and m meetings overall. Then we certainly need n(G-1) = P-1 (each person meets everyone else) and mG=nP (so the total number of person-meetings can be counted either way). (Sanity check, P=1, G=P and G=2 can 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-1 divides P-1 it’s not going to divide P unless G is 2 or P.
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 really stupid.
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 G to divide P as well as G-1 dividing P-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 tried to 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 before I 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; put p long tables in it like spokes and label the seats at each table 0..p-1 from the centre out. At each change, you look at the label l on your seat and move to the seat labelled l which is l tables clockwise from where you were. The 0‘s (the sitters) stay put in the middle, the 1–movers move round in steps of 1, the p-1-movers whizz round the rim so fast they look like they’re going backwards! When you’ve had p rounds of this, go find the others with the same label (in the same orbit) as yourself.
This works for primes p because the l-movers never see the same sitter twice: 0,l,2l,…,(p-1)l all have different remainders (ie table numbers) on division by p. (Check: if il = ap + b and jl = cp + b, then (i-j)l = (a-c)p with p>l and hence (i-j)>(a-c); so (i-j) and p must have a common factor strictly between 1 and p; oops.) To see that the l-movers don’t see the same l’-mover twice either, spin the room at rate l so 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…
Your email address will not be published.
© 2017 The Daily Grind
Theme by Anders Norén — Up ↑