Multiply your social success with some cunning calculations (Image: Vincent Villeret/Picturetank)
Want the formula for a perfect party? Meet the mathematicians who can solve your social problems, from who to kiss to bathroom etiquette
Advertisement
AS IF things haven鈥檛 been strange enough, there is someone sitting, smiling, at the door of the gent鈥檚 toilet. It鈥檚 already been a weird enough party 鈥� weirdly happy, given that it is celebrating a divorce. The only people who look hassled and serious are the people moving through the crowd, clipboards in hand. Apparently, they are something to do with how we are all going to take our leave at the end of the night.
The smiling toilet attendant also has a clipboard, and now he is out of his seat. 鈥淓xcuse me, sir,鈥� he says, brightly. He introduces himself and shows me the clipboard. Before I go in, wants to walk me through the optimal use of the urinals. Three minutes later, I open the door with a confident push. I inhale happily 鈥� there is none of the usual whiff of anxiety. Every man in here knows exactly where to pee.
Kranakis, of Carleton University in Ottawa, Canada, worked with of Wesleyan University in Middletown, Connecticut, to sort out this particular problem. Faced with a long row of urinals and a steady flow of users, the ideal scenario is to avoid having an immediate neighbour for the duration of your visit. 鈥淎ll men know this,鈥� says Kranakis. Sometimes, however, optimising your urinal choice in a busy men鈥檚 room is difficult.
It turns out that being first into the bathroom is a big responsibility. The next man in will always try to maximise the distance between him and any others. This leads to a complex equation whose outcome depends on that first choice. Choose badly and some poor man 鈥� maybe even you 鈥� will suffer a loss of privacy before it was .
鈥淚t turns out that being first into the bathroom is a big responsibility鈥�
To see why, let鈥檚 start from an empty row of n urinals. Things are trickiest when there is an odd number of urinals. If the first man in chooses an odd-numbered position, then (n+1)/2 men can enjoy some privacy. Yet if he chooses even, one fewer man can bag a secluded spot before the group reaches 鈥渟aturation鈥�. This describes not the state of the floor, but the point at which the next desperate bathroom entrant has no choice but to violate someone鈥檚 privacy. With an even number of urinals, it doesn鈥檛 matter if the first person selects an even or odd position, the saturation point is n/2 either way (see 鈥淭he urinal problem鈥�).
Once saturation is reached, and further men take positions at random, Kranakis can tell me how long my privacy will last. The end urinals are your safe haven 鈥� and the far end is the safest. That鈥檚 because if you are at, say, urinal 1 of 5, closest to the door, a fourth man is likely to take the closest free slot 鈥� urinal 2 鈥� invading your privacy. Had you chosen urinal 5, your privacy would have lasted a little longer.
鈥淚t does have applications elsewhere,鈥� Kranakis assures me on the way out. 鈥淎 surprising number of things involve optimised packing.鈥� Apparently, efficiently recombining strands of DNA or connecting myriad wireless devices to a router鈥檚 network are essentially the same problem as finding privacy in the men鈥檚 room.
Party-goers aren鈥檛 the only ones to have such thoughts. In 1984, computer scientist of Stanford University in California noticed that his department鈥檚 restrooms were equipped with two rolls of available toilet paper per cubicle. The idea is a good one on the face of it 鈥� when the paper from one roll runs out, there is another one ready. The problem is, the human mind can render this solution toothless. In a paper entitled , Knuth pointed out that some people will choose from the bigger roll, and some from the smaller one. It is important to know how this will affect the number of sheets left on one roll when the other runs out. If it is too small, people could still get caught short despite the provision of the extra roll.
The mathematics is easy for very small rolls and when each user chooses one sheet at a time. In the improbable case that both rolls have just two sheets, for instance, and two-thirds of people are 鈥渂ig choosers鈥�, the answer is that an impossible one and one-third sheets are left on average when one roll has run out. The big question is what happens as the number of sheets on a roll tends towards infinity? How much paper will be left on the roll that survives the longest?
Oddly, it doesn鈥檛 always depend on the number of sheets on a roll. It turns out that, if big-choosers are in the majority, the bigger roll鈥檚 eventual size is independent of the initial number of sheets. If most people are 鈥渓ittle-choosers鈥�, on the other hand, the number of sheets left on the surviving roll is directly proportional to the number it had when first placed in the cubicle (see diagram).
The object of these ruminations is, of course, to minimise the number of times the toilet attendant has to trudge around the cubicles replacing the paper. But, back at the party, we are all about to learn that minimising travel is not just a toilet attendant鈥檚 problem.
As the party nears the end, the clipboards are being used to herd departing guests into neat rows. The aim, apparently, is efficient kissing.
When a party breaks up, everyone moves around the room kissing everyone goodbye. The trouble is, there never seems to be an optimal way of getting the job done 鈥� it is too easy to leave someone out. Here, though, the algorithmic A-Team is on hand to police the puckering.
and three computer-scientist colleagues at Stony Brook University in New York have solved the problem. They as a rectangle divided into a grid. Each spot on the grid can only be occupied by one person, and people can smooch whenever they are in adjacent spots.
In a crowded, narrow hallway, two parallel lines of people facing each other works best, with everyone kissing the person opposite, then one line moving one space to their left (see diagram). In a bigger room, the optimal strategy is similar: form two opposite lines that snake past each other 鈥� when you reach a wall, you all turn like oxen ploughing a field and head back the way you came. For n people in a room, the kissing is complete after n moves.
Being computer scientists, the Stony Brook researchers are aware that not everyone is comfortable moving around a room full of people. That鈥檚 why they also analysed the case where a couple of socially paralysed 鈥渨allflowers鈥� stay still. In that scenario 2n-2 kissing cycles are necessary.
Although the kissing researchers modelled different sized groups of people, they only investigated rooms that were square or oblong. They didn鈥檛 consider rooms that take other shapes, or are dotted with kiss-impeding tables and chairs. 鈥淲e don鈥檛 know how to find solutions when there鈥檚 furniture in the room,鈥� Bender confesses.
Once the kissing is done, I still have one question for Bender: why all this merriment at a divorce party? 鈥淥h, that鈥檚 down to the Pruhs-Woeginger algorithm,鈥� he says, and points. 鈥淭hose guys.鈥�
of the Technical University of Eindhoven and of the University of Pittsburgh, Pennsylvania, are the guests of honour. And perhaps that鈥檚 not surprising. They have worked out the happiest way of allocating items after a divorce. All the separating individuals have to do is rank their belongings in order of preference 鈥� the algorithm does the rest.
They are not the first to suggest that mathematics can help in a divorce settlement. In fact, the work was inspired by New York University political scientist and mathematician of Union College, New York. Their work on 鈥�envy-free fair division鈥� demonstrated how to slice assets into ever-smaller amounts in order to distribute the spoils of divorce to everyone鈥檚 satisfaction.
However, living in the real world, Pruhs and Woeginger realised that not everything desirable can be usefully divided into infinitesimally small chunks. A house is not like a cake. Neither is a pension, or custody of children.
But the 鈥淒ivorcing Made Easy鈥� algorithm can nevertheless come in handy. It is possible in many circumstances to leave everyone feeling that they received a fair share of the pie 鈥� as long as you work with the value individuals assign to the items, rather than any absolute financial measure.
Each party ranks the items from the one they want most, to the one they care about least. Then, the algorithm begins its work. First, the husband gets the item that the wife likes least. Then the wife gets the item her soon-to-be ex-husband has least desire for. Hopefully, the rankings allow this process to carry on until everything is allocated. If that happens, looking at what they have and what their ex has, they will consider it a fair split. But it doesn鈥檛 work in every situation 鈥� especially if the husband and wife have similar preferences. 鈥淚t needs the partners to disagree sufficiently strongly on the value of the items,鈥� Woeginger admits.
Here, though, it clearly did work: our smiling, newly divorced hosts are waving us goodbye. What鈥檚 more, we have all enjoyed wonderfully comfortable comfort breaks and everyone has kissed everyone so efficiently that the taxis have barely set their meters running. If only somebody had been on hand to implement yet another mathematical classic, the stable marriage algorithm, I might not have been leaving alone.
鈥淓veryone has kissed so efficiently that the taxis have barely set their meters running鈥�
Maybe it is time I organised an algorithmic assembly of my own.
This article appeared in print under the headline 鈥淧arty like it鈥檚 n=1999鈥�
