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 2ⁿ. The solution is easily modified for the general case.

Number the guests from 1 to 2ⁿ. In round 1, all the guests numbered 1 to 2^{n - 1} get up, and walk clockwise around the table in synch with each other, clinking with each seated guest (numbered 2^{n - 1} + 1 through 2ⁿ) 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 2^{n - 1} to clink with each other, and all guests numbered 2^{n - 1} + 1 to 2ⁿ 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.