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 3 of 5: Prove the three-person recurrence
Previous stepNext step
r(m,n)≤r(m−1,n−1)+3r(m,n)\le r(m-1,n-1)+3
Detailed analysis

Take t=r(m−1,n−1)+3t=r(m-1,n-1)+3 people. If all tt form a clique, choose 2m2m of them. If all are isolated, choose 2n2n of them. Otherwise there are three people u,v,wu,v,w with u,vu,v acquainted but u,wu,w unacquainted. Remove these three; the remaining r(m−1,n−1)r(m-1,n-1) people contain either m−1m-1 acquainted pairs or n−1n-1 unacquainted pairs. Add uvuv in the first case or uwuw in the second, proving r(m,n)≤r(m−1,n−1)+3r(m,n)\le r(m-1,n-1)+3.