Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 7 down vote favorite

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.

share|improve this question
1  
Do they have to stand in a circle? If you had 4 people standing "in convex position" (that is, at the vertices of a convex quadrilateral), they'd need four rounds, since only one pair of diagonal opposites can shake at a time, but if they stand as a triangle with one in the middle they can do it in three rounds. – Gerry Myerson Aug 1 '11 at 1:24
1  
@Gerry Myerson: This is an interesting observation, but I assumed the circle because it can be easily generalized to $n$ people. The symmetry also makes it easier for distributed systems, since we wouldn't need leader election or further synchronization/consensus to make. – M. Alaggan Aug 1 '11 at 1:27
What do you mean exactly by a cross-over? I understand there must be a constraint, but the way I see it right now, your problem is that the n persons are standing still on the vertices of a regular n-gon (for instance), and you're saying that a round consists of linking the vertices with edges so that the edges don't intersect each other, for that would be a "cross-over". Am I right? – Patrick Da Silva Aug 1 '11 at 1:28
1  
If that is a cross-over, then perhaps you have the solution for $n$ smaller than $4$ and have a lower bound for $n > 4$ because the complete graph with $n$ vertices is not planar. Although that bound seems kind of trivial. – Patrick Da Silva Aug 1 '11 at 1:30
1  
Note that in the solution I posted, all edges are straight lines. – Gerry Myerson Aug 1 '11 at 2:05
show 3 more comments

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
Great. A solution for $n=2m-1$ is by inserting an "imaginary" person that when a person $a$ shakes hands with, $a$ sits idle instead. This would be an $n+1$ rounds solution. We don't know if an $n$ round solution exists for this case yet. – M. Alaggan Aug 1 '11 at 2:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.