I was in a group of 10 persons and we wanted to make a know-each-other-better game, so we did the following thing: 5 of us were standing in the middle (inner circle) and the other five were standing in the front of a person from the inner circle (this was the outer circle). There was another person (not from this group) asking 5 the questions. After each question, the outer circle would have to shift to the right. After the first round, we wanted to mix up and start another one, but we observed that a lot of the pairs from the first round were also again in the second round.

This made me think a bit at home. Given a group of $2n$ people, and two subsets of $n$ people from the original group, I want to know the answer to the following questions:

  1. With $n$ questions per round ($n$ shifts), how the people must re-arrange so that the cardinality of the intersection between the generated sets of pairs in the two rounds is minimum?
  2. Same question, but with $n - 1$ questions (shifts) per round

I think this is a really interesting problem and of course, it can be generalized using cyclic groups and combinatorics and the goal would be to find a permutation/function, but I wasn't able to figure it out.

Can some of you give me some ideas about this? Thanks!

  • $\begingroup$ Not clear pair whome? $\endgroup$ – Toni Mhax Aug 26 '18 at 13:58
  • $\begingroup$ @ToniMhax I am not sure what do you mean. We have a group of 2n people and we divide it in two subsets with n people each. In the first round, we create n pairs between those two groups and in the second round we choose another two subsets and create the pairs between them again. How should we choose the subsets in the second round so that the number of resulting pairs that were initially in the first group to be minimal? More naturally, how should we re-arrange ourselves so that everybody will talk with almost everybody? $\endgroup$ – Adi Aug 26 '18 at 14:09
  • $\begingroup$ There are plenty of ways your idea of in and out circle is good you fix a circle $n$ persons and you permute the outside other $n$'s so you can have any permutation with no fixed point. For exemple if you shift (turn) the outside circle you are doing a cycle. Just simply. Thanks for explaining. $\endgroup$ – Toni Mhax Aug 26 '18 at 14:22
  • $\begingroup$ Yeah, I forgot about mentioning that. In our exercise, the inner circle was fixed and the outer circle was shifting n times => n pairs. $\endgroup$ – Adi Aug 26 '18 at 14:24

Your Answer

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

Browse other questions tagged or ask your own question.