Solutions: 

The best solutions so far were all written by TJ Takei.

1. Suppose there are n cubicles starting at 0 (the math is easier that way, remember?). Take the workers in the even-numbered cubicles 0, 2, 4, 6, ... and have them meet their neighbors to the right in the first 10 seconds. Then have the workers in the odd-numbered cubicles 1, 3, 5, 7, ... meet their neighbors to the right in the second 10 seconds. Next, split the cubicles into group 0 =  [0, 1, 4, 5, 8, 9, 12, 13, ...] and group 1 =  [2, 3, 6, 7, 10, 11, 14, 15, ...]. In the next 10 seconds, have 0 meet 2, 1 meet 3, 4 meet 6, 5 meet 7, and so on. In the next 10 seconds after that, have 2 meet 4, 3 meet 5, 6 meet 8, 7 meet 9, and so on. In this way, every worker has met each right neighbor two away and therefore every left neighbor two away.

Now for the final 20 seconds. Split the cubicles into group 0 =  [0, 1, 2, 6, 7, 8, 12, 13, 14, ...] and group 1 = [3, 4, 5, 9, 10, 11, 15, 16, 17, ...]. In the next 10 seconds, 0 meets 3, 1 meets 4, 2 meets 5, 6 meets 9, 7 meets 10, 7 meets 11, 12 meets 15, ... In the final 10 seconds 3 meets 6, 4 meets 7, 5 meets 8, 9 meets 12, 10 meets 13, 11 meets 14, .... Thus each person meets all six neighbors in 60 seconds. This is minimum time a person can shake hands with 6 people.

2. For this solution, we will use the notion of modulus. (x mod y) is the remainder after we divide x by y. For example 16 mod 6 is 4 because dividing 16 by 6, one gets 2 with a remainder of 4. We could have used modulus in the first solution. For example, the group [3, 4, 5, 9, 10, 11, 15, 16, 17, ...] can be characterized by those cubicle numbers c such that (c mod 6) = 3 or (c mod 6) = 4, or (c mod 6) = 5.

As in the solution to the first problem, we will be making a series of two-way divisions into groups. We will start with a “Manhattan distance” of 1 first and then move up to greater distances.

Manhattan distance 1 greetings (with 4 neighbors.) Divide workers (x,y) (x:integer, y:integer) into two groups. Group 0 consists of those whose cubical x values have the property that (x mod 2) = 0. In group 1, (x mod 2) = 1. That is, all rooms are divided into vertical stripes having width 1. Let the people in group 0 move to the right one step to greet their neighbors and then return to their cubicles. Then have group 1 likewise move to the right one step. That's the "x phase.” Now for the "y phase": Divide workers into two groups. Those in group 0 have (y mod 2) = 0 and those in group 1 have (y mod 2) = 1. That is, all rooms are divided into horizontal layers with depth 1. Let the workers in group 0 move the upward in the y direction to greet their neighbors. Then the workers in group 2 move upward in the y direction to greet their neighbors.

It takes 40 seconds for every worker to meet his or her four one-room-away neighbors.

Manhattan distance 2 greetings (with 8 neighbors). The straight horizontals and verticals are handled as in solution 1. For the horizontals, the x coordinates for group 0 have the property (x mod 4) = 0 or (x mod 4 = 1). For group 1, (x mod 4) = 2 or (x mod 4) = 3. This will take 20 seconds. Similarly the y two-away neighbors will take 20 seconds. The new challenge is the diagonal neighbors. Intuitively, we want to move northeast twice and then northwest twice. The question is how to do that.

Here is the northeast part. As usual, divide workers into two groups. Group 0 cubicles have the property that [(x+y) mod 4] = 0 or [(x+y) mod 4] = 1. Group 1 cubicles have the property that [(x+y) mod 4] = 2 or [(x+y) mod 4] = 3. That is, all rooms are divided into negatively sloped diagonals bands. Let the group 0 workers move up and to the right (northeast direction) to their diagonal neighbors. Then let the group 1 workers do the same.

Here is the northwest part. Group 0 cubicles have the property that   [(x-y) mod 4] = 0 or [(x-y) mod 4] = 1. Group 1 cubicles have the property that [(x-y) mod 4] = 2 or [(x-y) mod 4] = 3. That is, all rooms are divided into positively sloped diagonals bands. Let the group 0 workers move up and to the left (northwest) to visit their diagonal neighbors. Then let the group 1 workers do the same.

Manhattan distance 2 takes a total of 80 seconds. Thus the total is 120 seconds, which is the minimum time a person can shake hands with 12 people.

3. We are going to make use of the fact that several people can share the same cubicle at the same time.

0, 1, 2 move to cubicle 3. 4, 5 also move to cubicle 3. At the same time, 6, 7, 8 and 10, 11 move to cubicle 9. So, everyone reaches at least 4 away from himself. Now, 6, 7, 8 move back to cubicle 6 as do 3, 4 and 5. At the same time 9, 10, 11 move to 12, as do 14, 15, 16. Then they move home. The total time is: (6 going to 9) + (6 going back to 6) + 3 (3 going back to 3). This gives a total of 9 seconds.

He considers six people at a time and calls them colors: Red (R), Blue (B), Magenta (M), Green (G), Cyan (C) and Yellow (Y). The colors repeat with the next six. Of course the G, C, and Y of one group must meet the r, b, m of the next group (the lower case group). We don't mean they are independent, but each group of six performs the same movement. The figure shows what each participant does over time. For example the Red participant goes one cubicle left (relative to its initial position) in second 1, then two by second 2, stays in that cubicle in second 3, then returns to one cubicle left by time 4, his original cubicle in time 5, one right by time 6, and back to his original cubicle by time 7, where he remains. The figure on the right shows that participant r meets g and c at time 2, c at time 3, C and M at time 6, and Y at time 7. I invite the reader to analyze the figure to see that in eight seconds, each person meets his or her six nearest neighbors.

Here is a paraphrase of TJ Takei's discussion of his strategy for this problem: 

To meet the neighbor 3 cubicles away, if they don't move and only I move, I move 3 steps up (or left) and 3 step down (or right) to meet the three-away neighbor in the opposite direction. Then I need to come back in 3 steps. That's nine steps. To reduce the number, far-away neighbors must move towards one another.

For example, if you focus on only Red and Cyan, they are left-right symmetric -- that is Red does 2 step moves and Cyan does a 1 step move to meet at time "2" in the first half. Then they switch directions to meet their counterparts at time "6". The action switching and symmetry are observed in Green-Yellow and Blue-Magenta pairs.

The rest is a series of careful local surgeries to intertwine these three pairs. Compare Red (or its up-side-down) with Blue and Green, they are almost the same except that the 1 step section has durations of 0, 1, and 2 respectively.

Further reading:
"Overview of neutral territory methods for the parallel evaluation of pairwise particle interactions," by Kevin J. Bowers, Ron O Dror, and David E. Shaw in The Journal of Physics: Conference Series 16 (2005) 300-304 SciDAC 2005.