Problem 5

Given positive integers

m

and

n

, find the smallest positive integer

k

such that among any

k

people, either there are

2m

people who can be divided into

m

pairs of mutually acquainted people, or there are

2n

people who can be divided into

n

pairs of mutually unacquainted people.

Step 2 of 5: Build the lower-bound example

Previous step Next step

(2m-1)+(n-1)=2m+n-2

Detailed analysis

Take a group of $2m+n-2$ people: a $(2m-1)$ -clique, together with $n-1$ isolated people who know nobody else. There are not $2m$ mutually acquainted people, and among the isolated people plus clique structure there are not $2n$ people forming $n$ mutually unacquainted pairs. Hence $r(m,n)\ge2m+n-1$ .