MathLabs

Problem 5

Given positive integers mm and nn, find the smallest positive integer kk such that among any kk people, either there are 2m2m people who can be divided into mm pairs of mutually acquainted people, or there are 2n2n people who can be divided into nn pairs of mutually unacquainted people.
Step 1 of 5: Exploit symmetry
Previous stepNext step
r(m,n)=r(n,m);m≥n⟹it suffices to prove r(m,n)=2m+n−1r(m,n)=r(n,m);\qquad m\ge n\Longrightarrow\text{it suffices to prove }r(m,n)=2m+n-1
Detailed analysis

Let r(m,n)r(m,n) be the least valid kk. Interchanging acquaintances and non-acquaintances exchanges mm and nn, so r(m,n)=r(n,m)r(m,n)=r(n,m). Assume m≥nm\ge n; the target becomes r(m,n)=2m+n−1r(m,n)=2m+n-1.