There are 5 students. Must form 3 teams and every team must have 2 students in common.

Question

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.

Answer 1

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$.)

Answer 2

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.

Answer 3

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.