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 4 of 5: Induct from the base case
Previous stepNext step
r(s,1)=2s,r(m,n)≤2m+n−1r(s,1)=2s,\qquad r(m,n)\le2m+n-1
Detailed analysis

The base case is r(s,1)=2sr(s,1)=2s: among 2s2s people, either there are 2s2s mutually acquainted people or two unacquainted people. Iterating the recurrence gives r(m,n)≤2m+n−1r(m,n)\le2m+n-1 when m≥nm\ge n. Combined with the lower bound, equality holds.