1
$\begingroup$

There are $2n$ persons shaking hands in turns. In every turn every person shakes hands with exactly one other person. After the turn all of them may choose another partner.

I'm searching for:

  • The minimal number of turns needed so that every person has shaken hands with all of the $2n-1$ other persons.
  • An algorithm that calculates a minimal sequence of turns.
$\endgroup$
  • $\begingroup$ Does each person shake their hands with all the other people in the party? $\endgroup$ – Gyanshu Jan 17 '17 at 17:21
  • $\begingroup$ Yes, each person shakes hands with all of the $2n-1$ other people. $\endgroup$ – zwirbeltier Jan 17 '17 at 17:24
  • $\begingroup$ it would take 2n-1 turns, starting in alphabetical order of names, the person would shake hands with the first person in alphabetical order that they have not shaken hands with, and is not selected to shake hands with anyone - then the next unselected person in alphabetical order would have the same applied to them $\endgroup$ – Cato Jan 17 '17 at 17:28
0
$\begingroup$

From wikipedia: https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

If $n$ is the number of competitors, a pure round robin tournament requires $\begin{matrix} \frac{n}{2} \end{matrix}(n - 1)$ games. If $n$ is even, then in each of $(n - 1)$ rounds, $\begin{matrix} \frac{n}{2} \end{matrix}$ games can be run concurrently, provided there exist sufficient resources (e.g. courts for a tennis tournament). If $n$ is odd, there will be $ n$ rounds, each with $\begin{matrix} \frac{n - 1}{2} \end{matrix}$ games, and one competitor having no game in that round.

The wikipedia entry goes on to provide a scheduling algorithm.

$\endgroup$
0
$\begingroup$

If there are $2n$ people then there must be $1+ \ldots + (2n-1) = n(2n-1)$ handshakes. Each turn we can do $n$ handshakes so we want to solve for $x$ in the following equation: $$ n(2n-1) - xn = 0. $$ If we do this we get $$ x = 2n-1 .$$

$\endgroup$
  • $\begingroup$ That's the lower bound, yes. Every person needs to do $2n-1$ handshakes. So at least $2n-1$ rounds are needed. But is there an actual sequence of turns that achieves this (for every person)? $\endgroup$ – zwirbeltier Jan 17 '17 at 17:51
0
$\begingroup$

would take $2n-1$ turns, starting in alphabetical order of names, the person would shake hands with the first person in alphabetical order that they have not shaken hands with yet and is not selected to shake hands with anyone in this turn - then the next unselected person in alphabetical order would have the same applied to them - this process would result in n handshakes per turn and would go through n-1 turns

for n = 2 : 4 people

if you had A,B,C,D

round 1

A-B

C-D

round 2

A-C (has shaken B's hand)

B-D (C is shaking hands)

round 3

A-D (only person left)

B-C

done!

$\endgroup$
  • $\begingroup$ How does this work for $n = 3$? $\endgroup$ – zwirbeltier Jan 17 '17 at 17:35
  • $\begingroup$ n can not be 3, since there are 2n people, an even number - if there was 3, then on each round there would be a person not shaking hands - so I'd have to think about that out of scope requirement $\endgroup$ – Cato Jan 17 '17 at 17:36
  • $\begingroup$ Of course it can. In my question $n$ is the number of pairs. So $n = 3$ means 6 people. $\endgroup$ – zwirbeltier Jan 17 '17 at 17:36
  • $\begingroup$ sorry I should have mentioned that, I put n=2 to give 4 people and 3 rounds in the answer $\endgroup$ – Cato Jan 17 '17 at 17:38
  • 1
    $\begingroup$ Ok. Your answer is for $n=2$. I doubt that the principle works for $n=3$ without needing more than $2*3-1=5$ rounds. $\endgroup$ – zwirbeltier Jan 17 '17 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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