126*. In the country's football championship, 20 teams are participating. What is the minimum number of games that must be played so that among any three teams, there are two that have already played against each other?
126. Answer: 90 games.

Let among any three teams, there be two that have already played against each other. Choose a team $A$ that has played the least number of games $-k$. Each of the $k$ teams that have already played with $A$, as well as team $A$ itself, has played no fewer than $k$ games. From the $(19-k)$ teams that have not played with $A$, each has played with all the other $(18-k)$ of them - otherwise, there would be a trio of teams, none of which have played against each other. Thus, the doubled number of all games - which can be obtained by summing the number of games played by all teams - is no less than,

$$
\begin{aligned}
k^{2}+k+(19-k)(18-k)=2 k^{2}-36 k+ & 18 \cdot 19= \\
= & 2(k-9)^{2}+180 \geqslant 180
\end{aligned}
$$

An example of a situation where 90 games have been played and the conditions of the problem are satisfied is given by two groups of 10 teams each, where all teams within each group have played against each other, but none have played against a team from the other group.

$\nabla$ If the teams are represented by points, and the teams that have not played against each other are connected by a segment, then the resulting graph, when the conditions of the problem are met, will be a triangle-free graph. It can be proven that in such a graph with $n$ vertices, the maximum number of edges is $\left[n^{2} / 4\right]$.

The reasoning conducted in the solution is similar to the proof of the "cross lemma" in solution 156 and the estimates in 246v).