How to shake hand with everybody as fast as possible? A relative of mine asked once an optimization problem to our friend. None of us found the solution. Here is a formulation of the problem.
Consider $2\times n$ board such that the squares of the form $(1,i)$ are empty and every square of the form $(2,i)$ contains one people per square, for all $1\leq i\leq n$. One says that two squares are adjacent if they have a common side.
If there are two adjacent squares that both has a people, they can shake hands. And if a given square has a people and its adjacent square has no people, he or she can move to the free square. People will move simultaneously so that $B$ can move to $A$'s current position if $A$ is going to move to another square at the same turn. On every turn, each people can either stay on his or her place, shake hands with one of his or her neighbor if he or she is not shaking hands with another people, or move to the adjacent square.
Is there a (closed form) formula how many turns it takes if all people wants to shake hands with every other people? Or any good upper bound? Or an algorithm that gives the optimal way to shake hands and move between squares?
 A: The answers until now are insufficient in the sense that just rotating the line only lets people meet others that are an odd number of squares away. An alternate solution would be to move the rows alternately and shake hands vertically after every move. For example (I move counter clockwise)


*

*Starting position
\begin{array}{|c|c|c|c|c|}
\hline
&  &  & & \\ \hline
1 & 2 & 3 & 4 & 5\\ \hline
\end{array}

*Move lower row
\begin{array}{|c|c|c|c|c|}
\hline
&  &  & & 5  \\ \hline
\enspace & 1 & 2 & 3 & 4\\ \hline
\end{array}

*Move upper row
\begin{array}{|c|c|c|c|c|}
\hline
&  &  & 5 &   \\ \hline
\enspace & 1 & 2 & 3 & 4\\ \hline
\end{array}

*Move lower row
\begin{array}{|c|c|c|c|c|}
\hline
&  &  & 5& 4  \\ \hline
\enspace & \enspace & 1 & 2 & 3\\ \hline
\end{array}

*Move upper row
\begin{array}{|c|c|c|c|c|}
\hline
&  & 5 & 4&   \\ \hline
\enspace &\enspace & 1 & 2 & 3\\ \hline
\end{array}

*Move lower row
\begin{array}{|c|c|c|c|c|}
\hline
&  & 5 & 4& 3  \\ \hline
\enspace & \enspace &  & 1 & 2\\ \hline
\end{array}

*Move upper row
\begin{array}{|c|c|c|c|c|}
\hline
&  5 & 4 & 3&   \\ \hline
\enspace &\enspace & & 1 & 2\\ \hline
\end{array}


This way everybody meets all the others once vertically. The total number of steps would then be bounded by $2(n-2)$ position swaps plus $2(n-2) + 1$ handshakes, which gives a total of $4(n-2) + 1$ actions.
A: I can imagine one possible algorithm, not knowing if it's optimal :


*

*at turn $1$, $(2,1)$ goes to $(1,1)$, every $(2,i)$ goes to $(2,i-1)$ for $2\le i\le n$. $(1,1)$ shakes hand with $(2,1)$.

*at turn $2$, $(1,1)$ goes to $(1,2)$, $(2,1)$ goes to $(1,1)$ and every $(2,i)$ goes to $(2,i-1)$ for $2\le i\le n-1$. $(1,1)$ shakes hand with $(2,1)$ and $(1,2)$ with $(2,2)$.

*... repeat the cycle until the $(2,1)$ reaches $(1,n-1)$.


This leads to $n-1$ turns of handshaking...
edit : I realize now that this doesn't work : each step makes people encounter someone $\mathbf2$ steps further, not one ! I realized this when I computed the number of effective handshakes : $p^2$ if $n=2p$, which is definitely not enough :-(
I will give this  more thoughts during my dentist session ;-)
end edit
To compute the minimal theoretical number of moves, you should solve $(n/2)^k\ge n(n-1)/2$, but I think this can be tricky with the rule exposed, if I understand it correctly.
