یک جدول $2 \times 8$ داریم. دو خانه را مجاور گوییم، اگر یک ضلع مشترک داشته باشند. میخواهیم تعدادی مهمان دعوت کنیم تا در خانه‌های جدول قرار گیرند. خبردار شده‌ایم ممکن است میان مهمان‌ها دزد یا دزدهایی موجود باشند؛ به همین دلیل میخواهیم در برخی از خانه‌ها به جای مهمان، نگهبان قرار دهیم. اگر دزدی مجاور دست‌کم یکی از نگهبانان باشد، شناسایی خواهد شد. حداقل چند خانه را باید با نگهبان پر کنیم تا در هر حالتی وجود یا عدم وجود دزد در جدول تشخیص داده شود؟
راهنمایی
ستون ها را از چپ به راست از ۱ تا ۸ شماره گذاری کنید حداقل به ۴ نگهبان نیاز داریم(چرا؟) و در با ۴ نگهبان در هر چهار خانه ی ستون ۲،۷ باید نگهبان باشد که خوب نیست(چرا؟)
پاسخ
گزینه‌ی ۱ درست است.
ابتدا مثالی با ۵ نگهبان ارائه میدهیم اگر ستون های جدول را از چپ به راست از ۱ تا ۸ شماره گذاری کنیم نگهبان ها به صورت زیر هستند: ستون ۲،۴،۶ نگهبان ندارند ستون ۱:خانه پایین ستون ۳:خانه بالا ستون ۵: خانه پایین ستون ۷: خانه بالا ستون ۸: خانه پایین حالا ثابت میکنیم باکمتر ۵ نگهبان نمی شود هر نگهبان با حساب خانه ی خودش حداکثر از ۴ خانه محافظت میکند پس حداقل ۴ نگهبان میخواهیم. از طرفی اگر دقیقا چهار نگهبان داشته باشیم نمی توانیم در خانه های گوشه نگهبان بذاریم چون در اون حداقل یک نگهبان حداکثر از ۳ خانه محافظت میکند و جمع خانه های محافظت شده به ۱۶ نمی رسد پس برای محافظت از خانه های گوشه باید در ستون های ۲ و ۷(شماره گذاری طبق مثال) هر دو خانه شان نگهبان بگذاریم که در این صورت خانه محافظت نشده باقی می ماند