So, decisions have been made on sessions for the BIG Event this year. Muggins here has somehow roped himself into convening an hour’s panel discussion (or somesuch) on project management, which is either going to be fun or (more likely) a bit of a nightmare. But at least I didn’t go down on my own – I took poor Ben with me. He’s been volunteered (by me, mostly) to run a meet/greet/pub trick session. The idea is a combination of a show & tell and speed dating. Or something like that.

The trouble is, there are likely to be a sizable number of people present, and we’d like everyone to meet everyone else. Precisely once. In groups.

As a result, we’ve both spent *hours* failing to spot the pattern. I think you can do it for a population *P* and group size *G* which satisfies *P* = *nG*(*G*-1), where *n* is the number of meetings. Then you just need to permute *n* sets of *G *identifiers (red/orange/yellow/… , triangle/square/pentagon/… , biped/quadroped/arthropod/… etc), print out those sets as cards, and hand them over to people. The rounds of meetings are thus ‘colours,’ ‘Number of sides,’ ‘number of legs,’ and so on. Job done. Unfortunately, my brain dribbled out of my ears just as I formulated this hypothesis. These days I can write, but I’m very, very rusty at this sort of stuff. Pathetic, really.

However, one of the fundamental aspects of my training as a physicist that I *do* recall, was to utilise tools appropriate to the circumstances. In this case: a mathematician. Conor, you’re up. I expect a neatly-argued and useful solution in the comments forthwith. Sadly, no LaTeX markup allowed.

Bonus marks to anyone who submits perl/ruby/PHP/python etc to generate the identifier patterns for me, and for alternative solutions. Particularly if they actually work, which mine probably doesn’t.

[update 3rd March: In an entirely expected development, Conor has written code in a language of which nobody else has heard. Meanwhile, a bit of gentle Googling has revealed this page, which suggests that what we’re looking at here is a form of Whist tournament. Which seems promising, until one stumbles over this page, which remarks on a failed brute force search for an 80-person solution.]

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…