در جمعی $n$ نفر حضور دارند. بعضی از این افراد همدیگر را می‌شناسند. فرض کنید که آشنایی یک رابطه‌ی دوطرفه است؛ یعنی اگر $a$ ٬$b$ را بشناسد، $b$ نیز $a$ را می‌شناسد. فرض کنید که هر نفر در این جمع حداکثر با $d$ نفر دیگر آشناست.

اگر $d=k+l+1$ باشد، می‌خواهیم این افراد را به دو گروه $A$ و $B$ تقسیم کنیم به‌ طوری‌ که هر یک از اعضای گروه $A$ حداکثر $k$ نفر از دیگر اعضای این گروه را بشناسد و هر یک از اعضای گروه $B$ هم با حداکثر $l$ نفر از دیگر اعضای این گروه آشنا باشد.

برای این منظور الگوریتم زیر پیشنهاد شده است:

ابتدا یک گروه‌بندی دل خواه $(A,B)$ را در نظر می‌گیریم. سپس در هر مرحله این کار را انجام می‌دهیم: اگر گروه‌بندی $(A,B)$ دارای شرایط مسأله بود، کار تمام شده است. درغیر این‌صورت یا یک نفر در $A$ وجود دارد که با بیش از $k$ نفر از اعضای گروهش آشنا باشد و یا یک نفر در گروه $B$ وجود دارد که با بیش از $l$ نفر از اعضای گروهش آشنا باشد. در هر یک از این دو حالت فرد مزبور را به گروه دیگر منتقل می‌کنیم.

ثابت کنید که این الگوریتم همواره به جواب می‌رسد.

• سوال قبل