2
$\begingroup$

Situation

There are 5 teams, assume they have 10 members per team.

Objective

Together, the members of each team should be matched pairwise with all opponents in the minimum number of rounds.

So, the members of team 1 should have talked to the 40 people that are not in their team.

Benchmark

Teams could trivially be scheduled in 5 rounds as follows, this is the solution to beat!

Round 1: 4 v 5 and 2 v 3 (Rest: 1)
Round 2: 1 v 3 and 2 v 4 (Rest: 5)
Round 3: 1 v 5 and 3 v 4 (Rest: 2)
Round 4: 1 v 4 and 2 v 5 (Rest: 3)
Round 5: 1 v 2 and 3 v 5 (Rest: 4)

The full contents of 4 v 5 in round 1 could in this case be the following 10 pairs:

Team 4 person 1 - Team 5 person 1
Team 4 person 2 - Team 5 person 2
...
Team 4 person 10 - Team 5 person 10

Challenge

Beat the benchmark, or explain why it can't be beaten.

Note that you do not keep the team 'together' in the solution, just remember that team members don't need to be matched with eachother.

Bonus

For bonus points, give/add an answer that works for 9 people per team.

$\endgroup$
  • 1
    $\begingroup$ Do you need each member of each team to meet with each member of every other team? For example, in round 1 of the benchmark are there 100 interactions between 4 and 5 (each member of 4 interacting with each member of 5). If so, how many interactions are permitted per round? What are the limitations of a single round? $\endgroup$ – hexomino Sep 6 '16 at 13:59
  • $\begingroup$ My guess is that each person can have 10 pairings per round, given the example? $\endgroup$ – Ivo Beckers Sep 6 '16 at 14:02
  • $\begingroup$ @hexomino No, basically team A can be considered consider to meet up afterwards and share all they have learned from their 1 on 1 interactions with the other teams. -- I have updated the benchmark example. $\endgroup$ – Dennis Jaheruddin Sep 6 '16 at 14:04
  • $\begingroup$ @IvoBeckers No, as the team needs to meet all members of other teams, but the individuals do not need to meet all members of other teams. $\endgroup$ – Dennis Jaheruddin Sep 6 '16 at 14:05
3
$\begingroup$

Given the information and criteria, I think it can be done in

$4$ rounds

as follows

Divide each team into two groups of five designated the $A$ and $B$ groups.

Round 1: $1A$ v $2B$, $2A$ v $3B$, $3A$ v $4B$, $4A$ v $5B$, $5A$ v $1B$
Round 2: $1A$ v $3B$, $2A$ v $4B$, $3A$ v $5B$, $4A$ v $1B$, $5A$ v $2B$
Round 3: $1A$ v $4B$, $2A$ v $5B$, $3A$ v $1B$, $4A$ v $2B$, $5A$ v $3B$
Round 4: $1A$ v $5B$, $2A$ v $1B$, $3A$ v $2B$, $4A$ v $3B$, $5A$ v $4B$.

Proof that this is the minimum

Each individual must meet at least one member from each group so that that group can learn about that individual. This means that the individual must at least go through four rounds on interactions. Hence, we must have at least four rounds.

Bonus

If the teams each have nine members, then there are a total of $45$ individuals. Hence, at each round there will be at least one individual who won't have any interaction.

Let $a$ denote a person who does not have any interaction in the first round. $a$ must meet at least one person from each group so that that group can learn all about $a$. Hence there must be at least another four rounds of interactions so that $a$ can meet every group.

Hence there must be at least five rounds and, in this case, the benchmark provides an optimal solution.

$\endgroup$
  • $\begingroup$ Very nice! As this got solved quicker than expected, I also added a bonus part. Be sure to check it out! $\endgroup$ – Dennis Jaheruddin Sep 6 '16 at 14:23
1
$\begingroup$

My answer would be

4 rounds

Explanation

Round 1 : Half of team 1 players will pair with half of team 2 players and rest half will be paired with half of team 5 players. Rest of team 2 players will pair with half of team 3 players... and so on.

Round 2 : Now pairing will be reversed. Players of team 1 who were paired with team 2 players will now be paired with team 5 players who were paired with rest on team 1 players . Ok let me Clear it more. Let's name those half teams as 1-1(players 1-5 of team 1) and 1-2(players 6-10 of team 1). So first round was 1-1:5-1 & 1-2:2-1, Now it would be 1:2-5:2 and 1-1:2-2. So after 2 rounds all players of team 1 have met all the players of team 5 as well as team 2.

Similar approach can be made for round 3 and 4 but this time team 1 would be paired with team 3 and team 4

$\endgroup$
  • $\begingroup$ Though it is not as clear as the answer by @hexonimo, I think this also works. Have a look at the bonus question! $\endgroup$ – Dennis Jaheruddin Sep 6 '16 at 14:25

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.