I've met a group of 9 colleagues (PhD students), and when we came to handshake it was complicated as always to handshake everyone and avoid cross overs.
So one guy suggested (he was not serious about it) to study the problem of the minimum number of rounds for a circle of $n$ friends to handshake such that no crossovers occur. Of couse the minimum if we allow crossovers is $n-1$ rounds, because if we fix a person, then in each round he gets to shake hands with at most one other person. But there is a moment where the two guys next to him shake hands, and so he sits idle in that round.
The natural question is if there is a formula for the least number of rounds needed in this case, or at least lower bound lower than the trivial bound where each person gets to shake hands with all others while everyone else stands still waiting for him to finish.
I am not expecting a solution but rather hoping if this problem has been studied before. When I tried searching I ran into all sorts of homework problems like "if 534345 handshakes happened then how many people were there" … I wasn't also sure of the search terms; I tried both "crossovers" and "intersection" but no avail.
Edit:
From the comments I realize that maybe more solid definition for the problem is needed. Here it goes:
There is a set $P$ of $n$ people positioned at the vertices of a regular $n$-gon. The goal is that after the "program" terminates, every person should have shook hands with every other person exactly once. By "shaking hands" we mean that two persons have a edge connecting them. The execution proceeds in rounds, such that at each round a person may be either "shaking hands" with another person, or doing nothing. A person $i$ who shook hands in some preceding round with a subset of people $J\subseteq (P-\{i\})$ will consider only the people he did not shake hands with yet $(P-(J\cup\{i\}))$ in the next round, by selecting one of them to shake hands with. The constraint is that at no round no two edges can intersect.
The question is to determine the minimum number of rounds needed to solve this problem ?
Also I would be interested in a special case where the edges are restricted to be "straight lines", rendering the constraint a little bit different from planar graph condition, to a more geometrical condition.
Best Answer
I don't know if it has been studied before, but I think this may be a solution for even $n=2m$.
Number the people around the circle from 1 to $2m$.
In round $j$, $1\le j\le m$, person $j$ shakes hands with person $j+1$, and all other handshakes are "parallel" to this (so, $j-1$ with $j+2$, $j-2$ with $j+3$, and so on - throughout, the labels are interpreted modulo $n$, as necessary). At the end of these $m$ rounds, everyone has shaken hands with everyone an odd number of people away.
In round $m+j$, $1\le j\le m$, $j$ shakes with $j+2$ and all other handshakes are parallel (so $j-1$ with $j+3$, $j-2$ with $j+4$, etc.). This handles all the pairs an even number of people apart. So the total is $2m$ rounds.
As noted in the problem statement, $2m-1$ rounds is impossible, so $2m$ is the answer.
EDIT: The odd case is even easier. In round $j$, person $j$ sits out while $j-1$ greets $j+1$, $j-2$ greets $j+2$, etc., again using $n$ rounds.