Conference insanity

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

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

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

  4. 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…)

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

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

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

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

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

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

  11. 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 1movers 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…

Leave a Reply

Your email address will not be published.

*

© 2017 The Daily Grind

Theme by Anders NorénUp ↑