در کشور خیکولند ‎$n$‎ شهر وجود دارد و قرار است ‎$n-1$‎ شرکت هواپیمایی ‎$T_1$‎, ‎$T_2$‎, ‎$\cdots$‎, ‎$T_{n-1}$‎, برقراری ارتباط هوایی بین این شهرها را به عهده بگیرند. در ضمن می‌دانیم شرکت ‎$T_i$‎ قرار است مدیریت ‎$i$‎ خط هوایی را به عهده بگیرد (هر خط هوایی ارتباط دو شهر را در دو جهت رفت و برگشت پوشش می‌دهد). همچنین می‌دانیم شرکت ‎$T_i$‎ برای انتخاب ‎$i$‎ خط هوایی خود یکی از دو الگوی زیر را در نظر گرفته است:

1. ‎‎ الگوی ستاره: یک شهر توسط ‎$i$‎ خط هوایی به ‎$i$‎ شهر دیگر وصل می‌شود.
2. ‎‎ الگوی مسیر: ‎$i$‎ خط هوایی تشکیل یک مسیر به طول ‎$i$‎ را می‌دهند و ‎$i+1$‎ شهر را متوالیاً به هم وصل می‌کنند.

ثابت کنید الگوهای انتخابی شرکت‌ها هر طور باشند می‌توان ارتباط هوایی شهرها را بین این شرکت‌ها طوری تقسیم‌بندی کرد که بین هر دو شهر, دقیقاً یک خط هوایی برقرار باشد.

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