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