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.