گزینه‌ی ۴ درست است.

اگر قبیله‌ای به یکی از قبیله‌های همسایه‌ی خود حمله نکند آن را ایمن ساخته است. مثالی وجود دارد که تمام قبیله‌ها ایمن خواهند شد. در این مثال هر قبیله دقیقا به یکی از قبایل همسایه‌ی خود حمله نمی‌کند.

می‌توان با استفاده از قبیله‌های شماره‌های ۳، قبیله‌های شماره ۴ را ایمن ساخت.

می‌توان با استفاده از قبیله‌های شماره‌های ۴، قبیله‌های شماره ۲ را ایمن ساخت.

می‌توان با استفاده از قبیله‌های شماره‌های ۲، قبیله‌های شماره ۳ را ایمن ساخت.

گزینه‌ی ۲ درست است.

همانند روش قبل باید حداقل قبیله را انتخاب (ایمن) کنیم که هر قبیله‌ای با حداقل یکی از آنها همسایه باشد.

در صورتی که قبیله‌ها با شماره‌ی ۴ را انتخاب کنیم شرایط مسئله برآورده می‌شود. اثبات می‌کنیم با کم‌تر از ۶ قبیله نمی‌توان به هدف رسید:

برهان خلف. فرض کنید که با انتخاب ۵ قبیله بتوان به مقصود سوال رسید. قبیله‌ها را مانند زیر تقسیم‌بندی کنید. طبق اصل لانه‌ی کبوتری از یک بخش قبیله‌ای انتخاب نمی‌شود (مثلا بخش بالا چپ). در نتیجه باید خانه‌‌ی $A$ و یکی از قبیله‌های مجاورش ($B$ یا $C$) را انتخاب نمود. به همین صورت باید یکی از قبیله‌های $D$ یا $E$ نیز انتخاب شود (که در هر صورت $D$ انتخاب بهتری خواهد بود) همچنین یکی از همسایه‌های آن نیز باید انتخاب شود که در هر حال $F$ انتخاب بهتری خواهد بود. در نتیجه در ادامه با انتخاب یک قبیله‌ی دیگر نمی‌توان شرایط را برآورده کرد. پس حداقل انتخاب ۶ قبیله لازم است.

در نتیجه حداکثر تعداد قبیله‌های تنها برابر ۱۲ خواهد بود.