3. we call two people a friendly couple if they know each other, and we call them a non-friendly couple if they do not know each other (being friends or not being friends is always mutual). Let $m, n$ be natural numbers. Find the smallest natural number $k$ such that the following holds: In every group of $k$ people there are always $2 m$ people who form $m$ disjoint friendly pairs, or there are $2 n$ people who form $n$ disjoint nonfriendly pairs.
## Solution

The smallest value is $k=\max \{m, n\}+m+n-1$. Due to the symmetry of the problem, we can assume $m \geq n$.

We first prove that $k \geq 2 m+n-1$ holds by specifying a configuration with $2 m+n-2$ people that does not fulfill the conditions of the task. Consider a group $X$ of $2 m-1$ people who all know each other, and a group $Y$ of $n-1$ people who do not know any of the other $2 m+n-3$ people. Each friendly pair lies entirely in $X$, so there are at most $\lfloor|X| / 2\rfloor=m-1$ disjoint such pairs. In every unfriended pair, at least one of the people is in $Y$, so there are also at most $|Y|=n-1$ disjoint such pairs.

We now show inductively $k \leq 2 m+n-1$.

- The anchoring $n=1$ is trivial: Either there is a non-friended pair or all $2 m$ people know each other.
- Induction step $(m, n) \rightarrow(m+1, n+1)$. We therefore assume that the assertion holds for $(m, n)$ and consider a friendly group of $2(m+1)+(n+$ 1) $-1=(2 m+n-1)+3$ people. If they all know each other, then there are certainly $m+1$ disjoint pairs of friends. If all of them do not know each other, then there are certainly $n+1$ unfriended pairs. We can therefore assume that three people $A, B, C$ exist, so that $A$ and $B$ know each other, but $B$ and $C$ do not know each other. Among the remaining $2 m+n-1$ people, there are now $m$ disjoint friendly pairs or $n$ disjoint nonfriendly pairs according to the induction assumption. In the first case, $(A, B)$ is another disjoint friendly pair,
in the second case, $(B, C)$ is another disjoint unfriended pair. This completes the induction.