There are 6 teams $E_{1},E_{2},....,E_{6}$ and each team has to have a meeting to discuss about something. How many hours are needed (minimum) so that all the meetings have been done, when: \begin{align*} E_{1}&=\{A,B,C\} \\ E_{2}&=\{A,D,E\} \\ E_{3}&=\{B,C,Z\} \\ E_{4}&=\{Z,H,T\} \\ E_{5}&=\{E,H\} \\ E_{6}&=\{D,E,T\} \end{align*} ?
Asked
Active
Viewed 61 times
1
-
2Could you clarify your question? Do the teams have to meet with each other or just with themselves? Also, how many teams can meet at the same time? – Ragnar Jan 25 '14 at 15:44
-
1One hour is not enough, because then $A$ would need to be in two meetings at the same time. – vadim123 Jan 25 '14 at 15:45
-
1Ah, the problem is that some teams have common members and thus can't meet at the same time. – Ragnar Jan 25 '14 at 15:45
-
1Oh, I thought $A, \ldots Z$ were the topics of the meetings?! – Hagen von Eitzen Jan 25 '14 at 15:46
-
1How many hours each meeting lasts? – CAGT Jan 25 '14 at 16:08
2 Answers
3
The teams are vertices of a graph and join vertices (i.e. meetings) if they share members. The task is to determine the cromatic number $\chi$ of that graph.
We have $\chi\ge 3$ because of odd cycles like $$E_4\stackrel{H}\longrightarrow E_5\stackrel{E}\longrightarrow E_6\stackrel{T}\longrightarrow E_4 $$ and $$ E_1\stackrel{A}\longrightarrow E_2\stackrel{D,E}\longrightarrow E_6\stackrel{T}\longrightarrow E_4\stackrel{Z}\longrightarrow E_3\stackrel{B,C}\longrightarrow E_1.$$ On the other hand, three colours (and hence three hours) suffice, e.g. $$\{E_1, E_5\}\quad\{E_2,E_4\}\quad \{E_3,E_6\} $$
Hagen von Eitzen
- 374,180
2
Assuming the problem is that some people are a member in multiple teams and therefore those teams can't meat at the same time, it isn't hard to see that only two teams can meet at any moment. (One way to see this is that any two of $E_1$, $E_2$ and $E_3$ have a common member and the same for the remaining three teams. Only $E_2$ and $E_3$ could meet at the same time, but then, none of $E_4$, $E_5$ and $E_6$ can meet.)
Thus, we need at least $3$ rounds, where during every round, one of the first three and one of the last three teams is meeting. It can be seen that $E_2$ can only meet at the same time as $E_4$ in that case. Then we can pair $E_1$ and $E_3$ with $E_5$ and $E_6$ in some way. Thus, it can be done in three hours.
Ragnar
- 6,233