This page is about an icebreaking event that I organised for the British Interactive Group (BIG) Event held in Manchester in July 2006. The idea arose from my wish that more people would bring demos and other physical "stuff" along to the BIG Event, and Jonathan Sanderson's thought that a speed-dating-type event would be a good icebreaker for the BIG Event.
The intention was to arrange things so that each participant would meet as many other people as possible, and also that everybody should bring along a demonstration or some other thing of interest from their work. With the numbers involved (about 90) and the time available (an hour) it wasn't going to be possible to have meetings à deux, so I people met in 20 groups of five. For 5 minutes, each group did introductions and demos within the group. Then on a signal (a balloon bursting), everyone reshuffled into new groups, and the procedure was repeated. The groups on each cycle of the event were prearranged, and everyone had a unique instruction sheet which told them where to go and when (see later).
I knew that in the time available, each person would not be able to meet everyone. In fact, with groups of 5, and 10 "rounds", each person could meet no more than 40 people. Nevertheless I naively hoped that I could arrange that nobody would meet anybody else twice. However, an hour or two's fruitless effort with ever-simplified versions of the problem told me that it wasn't going to be that easy.
Enter the Reverend Kirkman
If you can't do something, it's reassuring to discover that nobody else can do it either. And so it turned out. My demo-dating problem was one case of the delightfully-named
Kirkman's Schoolgirl Problem. The Kirkman in question is the
Reverend Thomas Penyngton Kirkman (1806-1895)
and the problem is named thus not because of the Rev. Kirkman's proclivities, but because of the way he set it as a puzzle in 1850 in the periodical The Lady's and Gentleman's Diary:
Fifteen young ladies of a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk abreast more than once.
You can almost smell the hockey sticks.
An unsolved problem in mathematics
There is a solution (seven of them, in fact) to the specific problem set by Kirkman, but there is no general method of solution for the class of related problems involving different numbers of people in groups of different sizes (also known as the Social Golfer Problem).
Now the problem I was trying to solve is a lot easier than Kirkman's Problem, because I wasn't trying to get everyone to meet everyone. Nevertheless, I still found myself mathematically challenged, and I therefore applied brute force. With about 1.5 × 10139 ways of running the event, checking every possible arrangement was out of the question. So I wrote a Python program that allocated people to groups randomly. It simulated several hundred thousand complete demo-dating events, and picked the one that produced the best result. For this arrangement, it turned out that:
Most people met 33 or 34 different people (out of a possible 40).
The luckiest person met 40 people once, and nobody twice.
The two unluckiest people met 31 different people.
There were 20 lettered stations around the room. The program produced a unique sheet for each participant that told them which stations to visit and in which order (see below).
Did it work?
Judging by feedback and by the fact that nobody could hear the balloons being burst, the demo-dating session was a great success. I have been asked to repeat it at the 2007 BIG Event.
At the request of one of the BIG participants, I did the arrangements for a similar event at the RoboFesta UK 6th Annual Open Meeting in October 2006.
Update, 11th March 2007
This morning I decided to try out a different method of allocating people to groups that was a bit more purposeful than the old method. I started with just two rounds of the demo-dating event, with people allocated randomly to groups. This arrangement was then scored by counting the number of times that two people met each other twice (we'll call this a duplicate meeting). Then a random pair of people was chosen (from different groups) in the second round, and they swapped groups. The new arrangement was scored again; if the score was better (fewer duplicate meetings) than before, the swap was retained, and otherwise it was reversed. This swapping procedure was repeated, keeping swaps only if they reduced the number of duplicate meetings, until the number of duplicate meetings was zero. Then a third round was added, with people allocated randomly to groups. The swap-and-score procedure was repeated, this time swapping people only in the third round, until the number of duplicate meetings was again zero. Then a fourth round was added, and so on until all 10 rounds had been done.
I had absolutely no right to expect this procedure to work. It depended upon getting to some target state (ten rounds with no duplicate meetings) by incremental changes, each of which had to reduce the number of duplicate meetings. It's a bit like climbing a hill in the mist by assuming that as long as every step you take is uphill, you'll reach the summit. Such a rule has a flaw: if the hill has a subsidiary summit, the procedure could lead you there, and your uphill-only rule would prevent you taking the necessary downward steps in order to reach the main summit. So I fully expected my procedure to get stuck with some group allocation that was locally optimal (such that no single swap could improve it) but not globally optimal (ie there were better group allocations to be had).
But it worked! My Python program (with no optimisation) took about 2 minutes to arrive at a group allocation that meant that nobody meets anybody else twice. This is a huge improvement compared to my old method, where only one person had a "perfect" event, and it's also about fifty times faster. As you might expect, it sorts out the first few rounds very quickly, and sweats a lot over getting rid of the last duplicate meeting in the last couple of rounds.
I cannot believe my luck.
(NOTE: This does not mean that I have a way of finding solutions to the general Kirkman's Schoolgirl Problem. I'm not trying to get everyone to meet everyone else exactly once, just no more than once. As it turns out, my program fails to solve the original 15-girl problem. It seems never to gets further than the 6th day.)
