شکل رو به رو کشور خیکولند را نشان می دهد که از ۱۸ قبیله تشکیل شده و قلمروی هر قبیله به شکل یک ۶-ضلعی است. طبق یک آیین دیرینه صبح روز مرحلهي اول هر قبیله به تعدادی از همسایه های خود حمله می کند. در شکل عدد روی قلمروی هر قبیله نشان دهندهي تعداد قبایلی است که این قبیله به آن ها حمله خواهد کرد. دو قبیله همسایه اند اگر و تنها اگر یک ضلع مشترک داشته باشند. یک قبیله تنها نامیده می شود اگر از طرف همهی همسایه های خود مورد حمله قرار بگیرد.
با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید:
حداقل چند قبیلهي تنها وجود دارد؟
پاسخ
گزینهی ۴ درست است.
اگر قبیلهای به یکی از قبیلههای همسایهی خود حمله نکند آن را ایمن ساخته است. مثالی وجود دارد که تمام قبیلهها ایمن خواهند شد. در این مثال هر قبیله دقیقا به یکی از قبایل همسایهی خود حمله نمیکند.
میتوان با استفاده از قبیلههای شمارههای ۳، قبیلههای شماره ۴ را ایمن ساخت.
میتوان با استفاده از قبیلههای شمارههای ۴، قبیلههای شماره ۲ را ایمن ساخت.
میتوان با استفاده از قبیلههای شمارههای ۲، قبیلههای شماره ۳ را ایمن ساخت.
حداکثر چند قبیلهي تنها وجود دارد؟
پاسخ
گزینهی ۲ درست است.
همانند روش قبل باید حداقل قبیله را انتخاب (ایمن) کنیم که هر قبیلهای با حداقل یکی از آنها همسایه باشد.
در صورتی که قبیلهها با شمارهی ۴ را انتخاب کنیم شرایط مسئله برآورده میشود. اثبات میکنیم با کمتر از ۶ قبیله نمیتوان به هدف رسید:
برهان خلف. فرض کنید که با انتخاب ۵ قبیله بتوان به مقصود سوال رسید. قبیلهها را مانند زیر تقسیمبندی کنید. طبق اصل لانهی کبوتری از یک بخش قبیلهای انتخاب نمیشود (مثلا بخش بالا چپ). در نتیجه باید خانهی $A$ و یکی از قبیلههای مجاورش ($B$ یا $C$) را انتخاب نمود. به همین صورت باید یکی از قبیلههای $D$ یا $E$ نیز انتخاب شود (که در هر صورت $D$ انتخاب بهتری خواهد بود) همچنین یکی از همسایههای آن نیز باید انتخاب شود که در هر حال $F$ انتخاب بهتری خواهد بود. در نتیجه در ادامه با انتخاب یک قبیلهی دیگر نمیتوان شرایط را برآورده کرد. پس حداقل انتخاب ۶ قبیله لازم است.
در نتیجه حداکثر تعداد قبیلههای تنها برابر ۱۲ خواهد بود.