The math behind galli cricket teams, and other interesting diversions

Group Theory in the Bedroom and Other Mathematical Diversions is Brian Hayes's set of collected essays from the American Scientist.

Full marks for the slightly risque title that will pique anyone's interest, but the book has nothing to with mathematics of partner swapping. The subject of the investigation is to find the golden rule for mattress flipping. Mattresses should be flipped periodically to ensure that all sides of the mattress get equal wear. It's easy enough to see that there are 4 possible configurations: (Side A, Side B) x (Top, Bottom). The goal is to find one rule, or a set or rules, that you can apply each time to perform a set of operations that ensures that you end up cycling through all 4 configurations.

If you only flip (along the long or short axis) you cycle through only two sides - A and B. If you only rotate in a plane then you cycle through - Top and Bottom. Using group theory, Hayes shows why there is no golden rule. You cannot perform the same set of operations again and again because the mattress is a Klein-4 group . A rotate and a flip along the short axis is the same as a flip on the long axis. Any set of two operations are equivalent to one operation. This proves to be the undoing of any rule, as we know that any ONE set of operations is not enough to cycle through all 4 configurations. So, you either need a fixed schedule, or a set of markers to ensure you do an opposite set of operations.

Being a kinda random fellow, I best liked Hayes's analysis of the effects of random flipping. If you randomly performed any one operation on a quarterly-basis then, on average, one side will get 31% of the wear instead of ideal 25%. A rather tolerable discrepancy of 6%. Then he goes on to discuss tire rotation and shows why that is completely different beast since it is a cyclic-4 group and hence there is a golden rule - "quarter turn clockwise (or anti-clockwise)".

What is most interesting about the book is that all these mathematical diversions start as anecdotes and rather innocuously. Consider the problem of partitioning a set of players into two teams: a problem that is encountered and solved on thousands of galli cricket and football 'fields' every day. The usual practice is to select two captains who then toss to decide who picks first. Then they go turn-by-turn to pick the rest of the players. Naturally, the players are chosen in order of ability. In general, this rule results in fairly balanced teams. Hayes calls this the Greedy Algorithm, because at each step the largest number (if you assigned numerical values to the strengths of the players) is chosen in each partition. In reality, of course this partitioning problem is quite a hard one, more technically, it's an NP complete problem and there are number of other algorithms, including the Karmarkar-Karp difference algorithm, but no optimal one. Then Hayes goes on to show why this does not matter on the playing field because on a log scale, abilities don't differ that much between strongest and weakest players and the simple 'greedy' partitions are reasonable without the need for fancy partitioning.

I greatly enjoyed reading the other chapters on namespaces, gear train ratios, and finding the continental divide. If only, mathematics was taught this way in schools.

Speed dating issues

I would like to think that my dating days aren't over, but just in a perpetually suspended state. However, I was at a speed-matching event yesterday which attempted to have a bunch of people meet everybody else one-on-one in a space of an hour.



First, there were only fifteen ppl and it was apparent that at every round someone would have to sit out. Then another guy showed up and we were sixteen. Since that was an even number no one would have to sit out. The person in charge did the obvious thing - he made two concentric rings of chairs splitting ppl two groups - 'inners' and 'outers'. The 'outers' rotated around the inner ring. After the first rotation, everybody had met half of the people in the group, except the ppl in their own ring. Then he did the next obvious thing, made another two concentric circles of the rings themselves and repeated the process. After the second rotation, everybody had met 3/4th of the ppl. For the next round, these rings needed to be split further into similar rings. As you can see, this process stops when each of the two concentric rings have exactly one person.

Of course, since we had the fourth power of 2, i.e. 16 ppl, this scheme works beautifully. Since, I was part architect of the idea, I wondered if this arrangement would work for other even numbers, leaving the rather odd case of odd numbers aside for now. Very quickly, you can see that this scheme breaks down for 6 people.

Round I            Round II
A D             A-B       D-E
B E             C (sits out)       F (sits out)
C F

After the first rotation, you have Ring I meet everyone in Ring II. Proceeding as before, you end up with 3 ppl (an odd number) in each new sub-ring. Now every subsequent iteration will have one person in each group simply sitting one session out. As you can see from the example, we can form a pair with C and F in Round II, but they have already met each other in Round I. So, every subsequent period, one person will be sitting out and wasting his time. This would require 6 time periods.

Thus, the concentric circles thing is inefficient for all non 2ⁿ even numbers. I tried to come up with a pairing scheme for n=6. Since ⁶C₂ = 15 total pairs, and we have 3 pairs at each stage, we should need at a minimum five rounds. With the schedule below no one sits out and we achieve efficiency.

Table for 6 ppl

Station	1	2	3	4	5
S1	AD	AE	AB	AF	AC
S2	BE	BF	CE	BC	BD
S3	CF	CD	DF	DE	EF

The movement of people is non-intuitive and the schedule is complicated. You would need to hand people a schedule map: A would not move at all. B would move to stations: S2-S2-S1-S2-S2. I was certain that there was a solution to this problem, floating in graph theory or combinatoric literature. And indeed there is! But, this is no simple can of worms as I was to discover.

Famously, in 1850 Reverend Thomas Kirkman sent a query to the readers of a popular math magazine, Lady's and Gentleman's Diary:

Fifteen young ladies in a school walk out 3 abreast for seven days in succession: it is required to arrange them daily, so that no two will walk twice abreast.

1 of 7 possible solutions

The more general case of problem is called the Social Golfer Problem: Determine the maximum number of days 'w' that 'n' golfers can play in groups of 'r' each without meeting each other. This is still an UNSOLVED mathematical problem!!! If you are interested in reading more see: Social Golfer Problem

My original question of dividing 'n' ppl in pairs has been solved at least up to n=200. Round-robin scheduling is a wonderful site for those scheduling matches, or speed-dating style events. There is no simple movement order that can be prescribed. You have to pretty much follow the schedule blindly. Some schedules are unique, in other cases there are over 1000 solution, usually when 2ⁿ numbers are involved.

Yeah! Even speed-dating has issues!