یک اداره از $n$ بخش تشکیل شده است که هر بخش دارای یک نفر با عنوان مدیر بخش است. مدیر هر یک از این بخش‌ها $n$ نفر کارمند را تحت نظر دارد. هر یک از این افراد تنها در یکی از این بخش‌ها کار می‌کنند. (بنابراین هر یک از کارمندان تنها تحت نظر یک مدیر است.)

می‌خواهیم برای هر یک از افرادی که در این اداره کار می‌کنند (یعنی مدیران بخش‌ها و کارمندان) یک دفتر کار اختصاص دهیم به‌طوری‌که شرایط زیر برقرار باشند:

• هر یک از این افراد یک دفتر داشته باشد. البته هر یک از دفترها می‌تواند هر تعداد از این افراد را در خود جای دهد.

• هیچ دو مدیری نباید باهم در یک دفتر قرار بگیرند.

• دفتر مدیر هیچ‌یک از بخش‌ها نباید با دفتر هیچ‌یک از کارمندان همان بخش یکی باشد.

• هر یک از مدیران باید با یک خط تلفن اختصاصی با هر یک از کارمندان زیر نظرش در ارتباط باشد. منظور از یک خط تلفن اختصاصی بین مدیر $a$ و کارمند $b$، خط تلفنی است که بین دفتر کار این دو کشیده شده است و از طریق آن تنها این دو نفر می‌توانند با هم صحبت کنند و هیچ‌کدام از سایر کارمندان و مدیران نباید از این خط استفاده کنند.

• بین هر دو دفتر کار حداکثر یک خط تلفن می‌توان کشید.

ثابت کنید که حداقل تعداد دفترهای لازم برای جا دادن این افراد به‌طوری‌ که شرایط فوق برقرار شوند برابر است با $\lfloor \frac {3n}2 \rfloor + 1$. (منظور از $\lfloor x \rfloor$ بزرگ‌ترین عدد صحیح کوچک‌تر یا مساوی با $x$ است.)

• سوال بعد
• سوال قبل