How to minimize the cardinality of the intersection of two sets of pairs from a cyclic group?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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:
- 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?
- 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!
combinatorics number-theory elementary-set-theory permutations cyclic-groups
asked Aug 26 at 13:32
Adi
113
add a comment |Â
up vote
2
down vote
favorite
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:
- 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?
- 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!
combinatorics number-theory elementary-set-theory permutations cyclic-groups
asked Aug 26 at 13:32
Adi
113
Not clear pair whome?
– Toni Mhax
Aug 26 at 13:58
@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?
– Adi
Aug 26 at 14:09
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.
– Toni Mhax
Aug 26 at 14:22
Yeah, I forgot about mentioning that. In our exercise, the inner circle was fixed and the outer circle was shifting n times => n pairs.
– Adi
Aug 26 at 14:24
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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:
- 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?
- 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!
combinatorics number-theory elementary-set-theory permutations cyclic-groups
asked Aug 26 at 13:32
Adi
113
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:
- 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?
- 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!
combinatorics number-theory elementary-set-theory permutations cyclic-groups
asked Aug 26 at 13:32
Adi
113
edited Aug 26 at 14:04
asked Aug 26 at 13:32
Adi
113
asked Aug 26 at 13:32
Adi
113
asked Aug 26 at 13:32
Adi
113
113
Not clear pair whome?
– Toni Mhax
Aug 26 at 13:58
@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?
– Adi
Aug 26 at 14:09
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.
– Toni Mhax
Aug 26 at 14:22
Yeah, I forgot about mentioning that. In our exercise, the inner circle was fixed and the outer circle was shifting n times => n pairs.
– Adi
Aug 26 at 14:24
add a comment |Â
Not clear pair whome?
– Toni Mhax
Aug 26 at 13:58
@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?
– Adi
Aug 26 at 14:09
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.
– Toni Mhax
Aug 26 at 14:22
Yeah, I forgot about mentioning that. In our exercise, the inner circle was fixed and the outer circle was shifting n times => n pairs.
– Adi
Aug 26 at 14:24
Not clear pair whome?
– Toni Mhax
Aug 26 at 13:58
Not clear pair whome?
– Toni Mhax
Aug 26 at 13:58
@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?
– Adi
Aug 26 at 14:09
@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?
– Adi
Aug 26 at 14:09
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.
– Toni Mhax
Aug 26 at 14:22
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.
– Toni Mhax
Aug 26 at 14:22
Yeah, I forgot about mentioning that. In our exercise, the inner circle was fixed and the outer circle was shifting n times => n pairs.
– Adi
Aug 26 at 14:24
Yeah, I forgot about mentioning that. In our exercise, the inner circle was fixed and the outer circle was shifting n times => n pairs.
– Adi
Aug 26 at 14:24
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2895044%2fhow-to-minimize-the-cardinality-of-the-intersection-of-two-sets-of-pairs-from-a%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Not clear pair whome?
– Toni Mhax
Aug 26 at 13:58
@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?
– Adi
Aug 26 at 14:09
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.
– Toni Mhax
Aug 26 at 14:22
Yeah, I forgot about mentioning that. In our exercise, the inner circle was fixed and the outer circle was shifting n times => n pairs.
– Adi
Aug 26 at 14:24