Saturday, October 13, 2012

Clinking Glasses in Linear Time

This is the kind of question that comes up when you have two theoretical computer scientists at the dinner table. Suppose there are N guests seated around a large table. If everybody wants to clink glasses with everybody else, and the time to clink is proportional to the distance around the perimeter of the table you have to travel to reach them, how can everybody clink with everyone else in time linear in N? You clearly can't do better than linear time, since every person takes up a certain minimum amount of space at the table, say at least 30 cm, so to reach the furthest person away you will need linear time.

On the other hand, there are N(N-1)/2 clinks to accomplish, so you will need some parallelism to do it all in linear time.

Here's how to do it. Let's say that the number of guests N is a power of 2, say 2n. The solution is easily modified for the general case.

Number the guests from 1 to 2n. In round 1, all the guests numbered 1 to 2n - 1 get up, and walk clockwise around the table in synch with each other, clinking with each seated guest (numbered 2n - 1 + 1 through 2n) as they pass them. Having completed a circuit of the table, they now sit down. This round costs N time.

It remains for all the guests numbered 1 to 2n - 1 to clink with each other, and all guests numbered 2n - 1 + 1 to 2n to clink with each other. This is done in the same way as before within each group, except now the guests don't make a full cycle of the table; they just go to the last guest in their group they need to clink with, and then in synch with the others, return back the way the came. The second round costs 2N/2 = N time.

In each subsequent round, the same thing is done, halving the sizes of the groups, so the distance each group has to travel halves as well. Thus further rounds cost N/2, then N/4, etc. So the total time elapsed is bounded by N + (N + N/2 + N/4 + ··· + 1) = 3N - 1.

Here's an example. Suppose there are 16 guests. In round 1, guests 1 through 8 get up, cycle around clinking with guests 9 through 16, who are seated. They make a full cycle of the table and sit down. Next, guests 1 through 4 get up and clink with seated 5 through 8; simultaneously 9 through 12 are up and clink with seated 13 through 16; they then return back they way the came. In round 3, guests 1 and 2 get up and clink with 3 and 4 and return; simultaneously 5 and 6 are clinking with 7 and 8; 9 and 10 are clinking with 11 and 12; 13 and 14 are clinking with 15 and 16. Finally, in the last round, each odd-numbered guest clinks with the person to the right. Here the total number of clinks is 8 · 8 + 2 · 4 · 4 + 4 · 2 · 2 + 8 · 1 · 1 = 120, which is (16 · 15)/2, as it should be.

4 comments:

D. Eppstein said...

There's a paper in FUN 2012 about a very similar problem: "The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye", by Michael Bender, Ritwik Bose, Rezaul Chowdhury and Samuel McCauley.

Joel said...

One algorithm that I think is fantastic came to my attention from the book "Hacker's Delight". It's to calculate the number of bits that are on in an integer (or whatever). It starts by summing each pair of bits. It then adds those sums together in each set of four bits, then adds them together into each eight bits, and so forth.

So it does what is obviously a linear operation in logarithmic time. Which is neat.

NIC1138 said...

The first iteration seems to be like when two opposing teams meet before a football or volleyball match, and each player shakes hands with all the other adversaries...

Jeffrey Shallit said...

NIC1138:

Exactly. You divide the guests into two teams who clink each other. Then each of the two teams divide into two, and do it again, etc.