At most how many handshakes could have taken place in a 20-member group, if we know that no matter how we select three people from the group, there are definitely two among them who did not shake hands?
Suppose in the company, $M$ shook hands the most (or at least one of those who shook hands the most), and let's denote the number of handshakes $M$ had by $m$. The $m$ people with whom $M$ shook hands could only shake hands with the other $(20-m)$ people (including $M$), because if any two of them shook hands with each other, adding $M$ to them would result in a group of three people, whose existence the problem excludes.

![](https://cdn.mathpix.com/cropped/2024_05_02_4129f18112a2bede4b17g-1.jpg?height=442&width=849&top_left_y=343&top_left_x=627)

Now let's count the handshakes by considering each one at both involved individuals. For those with whom $M$ shook hands, we can have at most $m(20-m)$ handshakes: $m$ people, each with at most $(20-m)$ handshakes. For the others (including $M$), we can count at most $m$ handshakes, and since there are $(20-m)$ of them, we again get at most $m(20-m)$ handshakes. In total, this is $2 m(20-m)$, but since we counted each handshake twice, the number of handshakes can be at most $m(20-m)$. This is maximized when $m=10$, so in the company, there can be at most 100 handshakes. This exact number of handshakes would occur, for example, if there were 10 women and 10 men in the company, and every woman shook hands with every man. In this case, no matter how we pick three people from the company, there will be two of the same gender who did not shake hands.

Remarks. 1. In our problem (and its solution), the number 20 has no special role. Generally, in a company of $n$ people, there can be $k(n-k)$ handshakes, where $k=\left[\frac{n}{2}\right]$. This theorem is due to Pál Turán and is one of the first results in graph theory. We can replace the number 3 in the problem with any other number, but this would result in a much more difficult question.

2. Many incorrect solutions were submitted for the problem. In these, the final result was often correct, but we could not accept them because they only showed that there is a company where 100 handshakes took place, and from this, no conclusion can be drawn regarding the question of the problem.