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.]
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…
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.
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.
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…)
No, let’s keep it simple – everyone’s involved in every round. I realise that this isn’t going to work for all P.
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.
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.
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!
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).
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?
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…