MathLabs

第5题

给定正整数 ,求最小正整数 ,使得任意 个人中,要么有 个人可分成 对彼此认识的人,要么有 个人可分成 对彼此不认识的人。 mm nn kk kk 2m2m mm 2n2n nn
第 1/5 步：利用对称性
上一步下一步
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
详细分析

令 r(m,n)r(m,n) 为满足条件的最小 kk。交换认识与不认识的关系会交换 mm 和 nn，故 r(m,n)=r(n,m)r(m,n)=r(n,m)。设 m≥nm\ge n，目标变为 r(m,n)=2m+n−1r(m,n)=2m+n-1。