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’t been strange enough, there is someone sitting, smiling, at the door of the gent’s toilet. It’s 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. “Excuse 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. “All men know this,” says Kranakis. Sometimes, however, optimising your urinal choice in a busy men’s 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 .
“It turns out that being first into the bathroom is a big responsibility”
To see why, let’s 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 “saturation”. 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’s privacy. With an even number of urinals, it doesn’t matter if the first person selects an even or odd position, the saturation point is n/2 either way (see “The 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’s 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.
“It does have applications elsewhere,” Kranakis assures me on the way out. “A surprising number of things involve optimised packing.” Apparently, efficiently recombining strands of DNA or connecting myriad wireless devices to a router’s network are essentially the same problem as finding privacy in the men’s room.
Party-goers aren’t the only ones to have such thoughts. In 1984, computer scientist of Stanford University in California noticed that his department’s 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 “big 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’t always depend on the number of sheets on a roll. It turns out that, if big-choosers are in the majority, the bigger roll’s eventual size is independent of the initial number of sheets. If most people are “little-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’s 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’s why they also analysed the case where a couple of socially paralysed “wallflowers” 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’t consider rooms that take other shapes, or are dotted with kiss-impeding tables and chairs. “We don’t know how to find solutions when there’s 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? “Oh, that’s down to the Pruhs-Woeginger algorithm,” he says, and points. “Those guys.”
of the Technical University of Eindhoven and of the University of Pittsburgh, Pennsylvania, are the guests of honour. And perhaps that’s 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’s 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 “Divorcing 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’t work in every situation – especially if the husband and wife have similar preferences. “It 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’s 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.
“Everyone 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 “Party like it’s n=1999″
