1
$\begingroup$

This is the problem.

Suppose there are 5 students and we are trying to form 3 distinct scientific teams such that

  1. Every student must join into at least one team (no student should left without a team)

  2. Every pair of teams must have exactly two students in common ($|A\cap B|=|A\cap C|=|C\cap B|=2$)

then in how many ways teams can be formed?


MY SOLUTION

I tried to solve it using stars and bars technique. here it is: ($t_i ,i=1,2,3$ stands for teams and $c_i; i=1,2,3,4,5$ stands for students)

$|T_1|T_2|T_3|$

For every student we need to select 2 bars and the $T$s between the bars equals to the teams he takes. So for each student there are $\binom {4} {2} = 6$ choices. The first problem with this reasoning is every student might be in 1 or 2 or 3 teams so it must be $\binom {3} {1} + \binom {3} {2} + \binom {3} {3} = 7$ not $6$! this is my first difficulty with this problem.

Second, whether 6 or 7 is correct (i don't know call it $x$), then I don't know for the rest of the students I should use rule of product ($x^5$) or rule of sum ($5x$)?

Third, I really have no idea how to calculate the second condition (2 students in common for each pair of teams). I just know it is principle of inclusion-exclusion and based on Grimaldi book (in this address page 400 of the book and 420 of the website page indicator) symbols :

If there there are $t$ conditions, then the number of objects that satisfy exactly $m$ conditions equals to :

$E_m = \sum_{k=0}^{t-m}(-1)^k\binom{m+k}{k}S_{m+k}$

if $S_i$ equals to number of students in common, I don't know how to calculate it.

$\endgroup$
  • $\begingroup$ Are you asking in how many way the teams can be formed? Otherwise, it is not really clear why you mention inclusion/exclusion in the title. $\endgroup$ – barak manos Mar 1 '15 at 20:14
  • $\begingroup$ @barakmanos Yes, let me update the question $\endgroup$ – M a m a D Mar 1 '15 at 20:18
2
$\begingroup$

Suppose first that some team, say $A$, has exactly two members, $c_1$ and $c_2$. Clearly $c_1$ and $c_2$ must both belong to teams $B$ and $C$ in order to meet the requirement that $|A\cap B|=|A\cap C|=2$. One of the remaining $3$ people must be on one of the remaining teams, and the other two must be on the third team. There are $3$ ways to choose the team with $2$ members, $\binom52$ ways to choose the $2$ members for it, $2$ ways to choose which of the remaining teams has $3$ members, and $3$ ways to choose that member from the remaining $3$ people, for a total of

$$3\cdot\binom52\cdot2\cdot3=180$$

divisions into teams of this type.

It’s impossible for one of the teams to have $5$ members; why?

Added: This question was based on the assumption that two teams could not have identical membership. If the question is interpreted to allow that possibility, there can indeed be a team of $5$ members; the other two teams must have $2$ members each and have identical membership. This adds $3\cdot\binom52=30$ possible divisions into teams.

Suppose now that no team has only $2$ members and that one team, say $A$, has $4$ members, $c_1,c_2,c_3$, and $c_4$; $c_5$ must be on a team that shares exactly $2$ members with $A$, so this team must have exactly $3$ members. For instance, it could be $B=\{c_1,c_2,c_5\}$. If $c_1$ and $c_2$ were in $C$, no other person could be in $C$, and $C$ would have only $2$ members, so $C$ can contain only one of $c_1$ and $c_2$. That means that $C$ must contain $c_5$ and exactly one of $c_3$ and $c_4$: why? In this case there are $3$ ways to decide which team gets $4$ members, and then $\binom54$ ways to choose the members of that team. Say that we’ve given team $A$ $4$ members. There are $\binom42$ ways to choose $2$ members of $A$ to combine with the fifth person to form team $B$. Finally, there are $2\cdot2$ ways to pick one of those $2$ members of $A$ and one of the other $2$ members of $A$ to combine with the fifth person to form team $C$. This gives us a total of

$$3\cdot\binom54\cdot\binom42\cdot2\cdot2=360$$

divisions of this type.

Finally, suppose that all teams have three members. Teams $A$ and $B$ must have exactly two members in common, so suppose that $A=\{c_1,c_2,c_3\}$ and $B=\{c_1,c_2,c_4\}$. Clearly $c_5$ must belong to team $C$. Moreover, $C$ must have two members in common with $A$, so either $c_1$ or $c_2$ must belong to $C$. Suppose that $c_1\in C$. That gives $C$ one member in common with $B$, but we need another; it must be either $c_2$ or $c_4$. If we put $c_4$ on team $C$, $c_1$ will be the only person on both $A$ and $C$, so we have to put $c_2$ on team $C$. Thus, $C=\{c_1,c_2,c_5\}$. This argument shows that there must be two people who are on all three teams, and each of the teams will contain exactly one of the other three people. There are $\binom52$ ways to choose the $2$ people who will be on every team, and there are $3!$ ways to assign the remaining $3$ people to the $3$ teams, for a total of

$$\binom52\cdot3!=60$$

divisions of this type and a grand total of

$$180+360+60=600$$

possible divisions. (I’m assuming that the teams have distinct identities — for instance, they’re studying different topics. If the teams are interchangeable, this result must be divided by $3!=6$.)

$\endgroup$
  • $\begingroup$ It is not right, $A = \{a_1,a_2,a_3\};B = \{a_1,a_2,a_4,a_5\};C = \{a_1,a_3,a_4\}$ this distribution satisfies the conditions but there are no two people an all three teams. $\endgroup$ – M a m a D Mar 1 '15 at 20:35
  • $\begingroup$ @Drupalist: You’re quite right: for some reason I was thinking that they had to be teams of $3$. Let me know when you’ve seen this, and I’ll delete the answer. $\endgroup$ – Brian M. Scott Mar 1 '15 at 20:37
  • $\begingroup$ Without thinking of the second condition, what is problem with my stars and bars reasoning? one of my reasoning leads to $6$ and the other one $7$ $\endgroup$ – M a m a D Mar 1 '15 at 20:43
  • $\begingroup$ I got it, it doesn't include the selection of $T_1$ and $T_3$ $\endgroup$ – M a m a D Mar 1 '15 at 20:53
  • $\begingroup$ @Drupalist: I don’t see any straightforward way to make your approach (of starting with the number of teams that each person is on) work. $\endgroup$ – Brian M. Scott Mar 1 '15 at 21:18
2
$\begingroup$

We can satisfy the intersection requirement in two ways: we can have two students common to all three teams and each other student on one team. Laars Helenius has shown that there are $270$ ways this can be done. He overcounts by $30$, because we are not allowed to put the three students that are each on one team onto the same one-the other two teams are identical. We can also have one student on all three teams, one student on each pair of teams, and one student on only one team. There are $5$ ways to select the common student, $4$ ways to select the student on only one team, $3$ ways to assign that student to a team, and $3!$ ways to distribute the other three, giving $360$, for a total of $600$ assignments. Note that we do not have enough students to have two students on each pair of teams and no student on all three teams.

$\endgroup$
  • $\begingroup$ I think Laars overcounted the first case by 210 not 30, because it's going to be $\binom {5}{2} \times 3! = 60$ , is it right? $\endgroup$ – M a m a D Mar 1 '15 at 22:25
  • $\begingroup$ @Drupalist: no, because having one team with just the two common ones, one team with one of the others, and one team with the last two is acceptable. The overcount is $5 choose 2$ ways to select the common two times $3$ ways to select the team that gets the other three. $\endgroup$ – Ross Millikan Mar 2 '15 at 0:54
1
$\begingroup$

I'm not certain it is all that complicated. Here is my attempt:

Since the the teams have to have two team members in common, there are $\binom{5}{2}$ ways to select the common members. The remaining three members can be selected to be on any of the three teams with $3^3$ ways of doing this. Thus $$ \binom{5}{2}\cdot 3^3= 270. $$

Notice that we cannot have any of the remaining members appear on multiple teams without upsetting the stated intersection requirement.

$\endgroup$
  • $\begingroup$ It’s not true that $|A\cap B\cap C|$ must be $2$; this condition is forced only if you require each team to have exactly $3$ members, as the OP just pointed out to me. $\endgroup$ – Brian M. Scott Mar 1 '15 at 20:39
  • $\begingroup$ Oh, I overlooked that. Hmm, I'll see if my approach is salvageable. $\endgroup$ – Laars Helenius Mar 1 '15 at 20:46
  • $\begingroup$ Note also that your argument counts arrangements in which two teams are identical. $\endgroup$ – Brian M. Scott Mar 1 '15 at 21:38
  • $\begingroup$ OK. Im leaving this answer up as Ross has referenced it, otherwise I would delete it at this point. $\endgroup$ – Laars Helenius Mar 1 '15 at 22:04

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.