8
$\begingroup$

Ok, let say Group A has N number of people, and Group B has M number of people.

I want each person in Group A to have a fixed T time conversation ( time T is fixed like 5 min or 10 min) with each person in Group B. That also means each person in Group B will have a fixed T time conversation with each person in Group A. People in the same Group will not talk to each other.

Requirement: How to match each person in Group A to the one in Group B in such a way that all people in Group A & B finishes all their conversations in shortest amount of time.

For example, Group A has 2 people, Group B has 4 people, time T is 5 mins. Suppose the conversation start from 16pm,

Then you can see this Matching pattern:

-From 16pm to 16:05pm, person 1 in Group A talks to person 1 in Group B, person 2 in Group A talks to person 2 in Group B. (ie person 3 & 4 in Group B will not have any conversation)

-From 16:05pm to 16:10pm, person 1 in Group A talks to person 2 in Group B, person 2 in Group A talks to person 1 in Group B. (ie person 3 & 4 in Group B will not have any conversation)

-From 16:10pm to 16:15pm, person 1 in Group A talks to person 3 in Group B, person 2 in Group A talks to person 4 in Group B. (ie person 1 & 2 in Group B will not have any conversation)

-From 16:15pm to 16:20pm, person 1 in Group A talks to person 4 in Group B, person 2 in Group A talks to person 3 in Group B. (ie person 1 & 2 in Group B will not have any conversation)

So, 20 min is the shortest amount of time in which all people in Group A can talk to all people in Group B.

The question is how to find the matching pattern with for N number of people in Group A, and M number of people in Group B, and T is one fixed conversation.

$\endgroup$
8
$\begingroup$

I think i found a simple solution, that is all people in the bigger Group will form a round circle, and all people in smaller Group will form an incomplete circle.

The people in the incomplete circle will go around in such a way that the 1st person will start from the beginning position (S) and finish in the (S - 1) position, see picture 1 and 2

I am not sure my solution is ok.

enter image description here

enter image description here

$\endgroup$
  • 3
    $\begingroup$ Yeah, this solution works. It's actually the same as mine, but I ramblingly elucidated the logic while you just drew an easy-to-understand diagram, XD $\endgroup$ – CaptainRad Sep 20 '14 at 20:12
4
$\begingroup$

The (or at least, an) optimal matching pattern is to take the larger group (or either if both are the same size), and pair each person in the larger group (we'll say group L) with their equivalent numbered person in the smaller group (group S), so person L1 talks to S1, L2 to S2, and so on. And members of group L that have no corresponding members of group S may be left out of the conversation round. Then, for the next round of conversations transpose the members of group L by one so that L1 talks to S2, L2 to S3, etc, with the last member of group L, LN, moving around to talk to S1. Again, members currently at the 'bottom' of the group L list will (assuming the 2 groups are not the same size), be left out of the rotation. Repeat the transposition/conversation process N times in total, so that at the end of the last conversation L1 is the last entry on the list of member of group L paired up against the ordered members of group S, and all members of each group will have talked to all members of the other group.

Thus, the total time taken is T*N, where N in the number of people in group L. It should be apparent that it is impossible to achieve the desired result in less than N conversations, since even if the smaller group contains only 1 person, she will have to talk to all N members of the larger group.

P.S: Sorry if that was a little rambling, but I hope it made sense.

$\endgroup$
  • 1
    $\begingroup$ so u mean like talk in a circle? this is interesting $\endgroup$ – Tom Sep 20 '14 at 18:06
  • $\begingroup$ Sort of? That's one way of representing it graphically anyway, as shown in the other answer. $\endgroup$ – CaptainRad Sep 20 '14 at 20:10

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.