8 teams play a tournament in which every team plays every other team exactly once. As the tournament goes, $k$ games have been held and ${8\choose 2}-k=28-k$ games are waiting. In all the cases that $k$ games are conducted, there always exists 3 teams among which no game has been held. What is the maximum value of $k$?
My try:
I want to solve this issue using probability. Namely, I want to get the probability $p$ that there exists 3 teams among which no game has been conducted, and let $p=1$ to get the range of $k$ that satisfying the condition. And since this is a discrete problem, I should retrieve the maximum value of $k$.
Specifically, there are $C_8^3=56$ combinations of 3 teams. If we number them from $1$ to $56$, and use $A_i, i=1,2,…,56$ to denote the event that there isn't any game among these 3 teams, we can get $p=P(A_1\cup A_2\cup…A_{56})$. Thus, the problem is changed to solve $P(A_1\cup A_2\cup…A_{56})$. Besides, I solve $P(A_i)=\frac{28-k}{28}\frac{27-k}{27}\frac{26-k}{26}$.
I have tried two ideas. The first is to use inverse event: $P(\cup_{i=1}^{56}A_i)=1-P(\cap_{i=1}^{56}\bar{A_i})$. However, $\bar{A_i}$ are not independent to each other. It is complex to compute the conditional probability here.
Thus, I try to solve it directly. Namely, $P(\cup_{i=1}^{56}A_i)=\sum\limits_{l=1}^{56}(-1)^{l+1}\sum\limits_{1<=i_1<…<i_l<=56}P(A_{i_1}…A_{i_l})$. And for each $l$, I can list all the possible number of teams involved and how many games are held in this case, but, in the same way, it is too complex.
I think there might be an elegant way to solve this issue. Methods beyond probability are welcome. Please help me, thank you!
Best Answer
Equivalently, you want to find the smallest $k+1$ so that there exists a subgraph $H$ of $K_8$ with $k$ edges that contains at least one edge from every $K_3$. This is a set covering problem, and the minimum turns out to be $k+1=13$. One such optimal subgraph with $12$ edges is $K_4 \cup K_4$.