5
$\begingroup$

$N$ people are at a party and decide to play a cooperative game. They begin by standing in a circle. The game proceeds in turns. In each turn, one person is chosen to perform one of the following actions:

  • Shake hands with someone adjacent to them
  • Swap positions with someone adjacent to them

The game ends when every pair of players has shaken hands, and the aim of the game is to minimize the number of swaps required. What is the optimal strategy?

I've tried working through some small examples (e.g. $N = 3,4,5,6$ require $0,1,3,5$ swaps minimum but I can't really find a pattern in the strategy).

$\endgroup$
  • $\begingroup$ 0 Swaps are required ... If everyone shakes the hand of the person adjacent to them, then no swaps are required. Do you mean to say that the purpose of the game is to minimize the number of turns? $\endgroup$ – Anthony P Dec 9 '16 at 6:12
  • $\begingroup$ If two people are standing on opposite sides of the circle, they will need to swap until they are adjacent so they can shake hands. $\endgroup$ – user2520385 Dec 9 '16 at 6:13
  • $\begingroup$ Oh I see ... Everyone must shake with everyone. $\endgroup$ – Anthony P Dec 9 '16 at 6:21
  • 2
    $\begingroup$ This is closely related to the "$f(n)$" question at math.stackexchange.com/questions/833541/… (I think there's just an extra $\binom{n}{2}$ rounds here from the handshakes). The question there wasn't answered, but there was a fairly long discussion in the comments. $\endgroup$ – Kevin P. Costello Dec 13 '16 at 23:19
  • 1
    $\begingroup$ I doubt that this has a simple solution. To play with: jsfiddle.net/zn1f30mv/5/show $\endgroup$ – leonbloy Dec 18 '16 at 1:28
-2
+100
$\begingroup$

Suppose $\{a_1, a_2, ...,a_n\}$ people play this game. The pairs of neighbours are

$$ \{a_1,a_2\} $$ $$ \{a_2, a_3\} $$ $$ \vdots $$ $$ \{a_n, a_1\} $$

Which gives $n$ pairs of neighbours. Swapping with a neighbour perturbs the set by

$$ \{a_1, a_2, ... a_{n-k+1}, a_{n-k}, ..., a_n\} $$

So that, now, $a_{n-k+1}$ can shake with $a_{n-k}$ (which presumably they already have) and (more importantly) shake with $a_{n-k-1}$

In order to shake with everyone, the person originally at location $n-k$ must migrate (by swapping) around the ring to position $n-k+3$ (and I assume this person shakes with everyone along the way).

We need a total of $\frac{n(n-1)}{2}$ handshakes, and each swap allows us to shake hands with 2 new people (one with the person who swapped, and one with the person who got swapped).

I will propose that $\left\lceil \frac{n(n-1)}{4} \right\rceil $ swaps will guarantee everyone has shaken hands, but I have not come up with a minimum expression.

Perhaps someone might take over.

$\endgroup$
  • $\begingroup$ As a courtesy, if somebody is going to "downvote" my answer, at least point out something I've done wrong or add something to it. Simply saying "this answer is not useful" without stating why is not useful. This is a community where we are all trying to learn. If you think I'm wrong, at least show me where. $\endgroup$ – Anthony P Dec 10 '16 at 4:22
  • $\begingroup$ It is not useful because: -this is not an answer; -there are some incorrect (or just meaningless) statements. You neither gave a strategy nor proved your amount to be minimal. $\endgroup$ – zhoraster Dec 10 '16 at 5:34
  • $\begingroup$ @zhoraster I showed that a number of swaps can guarantee that the game terminates, given everyone shakes in between swaps. If you have more to add to finding the solution, add it. $\endgroup$ – Anthony P Dec 10 '16 at 5:52
  • $\begingroup$ You didn't "show" this. You just "proposed" some number in the last paragraph. And you proposed in absolutely out of nowhere. If you really don't understand what is wrong in your post, I will try to help you. Concerning the last line of your comment, yes, I have more to find the solution and I had already added my comment. $\endgroup$ – zhoraster Dec 10 '16 at 6:07

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.