Problem
COM-B2-M06-P014 Ten People
#14
★★★★☆ Level 4 of 5
Prove that among any \(10\) people there are either \(3\) pairwise acquainted people or \(4\) pairwise unacquainted people.
Use the bound \(R(3,4)\le R(2,4)+R(3,3)\).
By Ramsey recursion,
\[R(3,4)\le R(2,4)+R(3,3).\]
Using \(R(2,4)=4\) and \(R(3,3)=6\), we get \(R(3,4)\le10\). Thus every red-blue colouring of the edges of \(K_{10}\) contains either a red \(K_3\) or a blue \(K_4\).
Translate this into people: red edge means acquaintance, blue edge means non-acquaintance. We get either \(3\) pairwise acquainted people or \(4\) pairwise unacquainted people.
Not the sharpest bound, but a very important one.