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 である。